在常数时间内找到堆栈中的最小元素

Question

如果我想在一个栈中（整数键）以常数时间找到最小元素，则可以按以下方式执行：

arr = [ 10, 7, 15, 12, 5 ] 

min_stack = []
main_stack = []

def get_min():
    if len(min_stack) < 1:
        return None
    return min_stack[-1]

def push(key):
    main_stack.append(key)
    if len(min_stack) < 1 or min_stack[-1] > key:
        min_stack.append(key)


def pop():
    key = main_stack.pop()
    min = get_min()
    if key == min:
        min_stack.pop()
    return key

for key in arr:
    push(key)    

在上述解决方案中，可以在使用大小为n的辅助存储器的情况下以O(1)的时间找到min值元素。但是否有一种方法可以利用整数键的算术属性，在不使用n大小的存储器或常量存储器的情况下完成此操作。

- anand

---

你只是想找到最小的元素吗？你可以在一个变量中存储最小的元素，并在每次推入元素时更新它。 - Haris

正如@Haris所提到的那样，您可以通过在每次更改堆栈时更新最小值的引用来保持对最小值的引用 - 例如，如果您推送或弹出某些内容，则检查并可能更新。但是，这意味着pop可能需要以O（N）时间运行，而不是传统堆栈的O（1）。如果您愿意使用堆将所有内容存储在堆栈中，您可以将其降至O（logN），但代价是内存。 - mgilson

相对于传统的 min()，具体有什么优势呢？ - Klaus D.

@ScottHunter中的“key”是唯一的整数。 - anand

@KlausD。我不想再过多讨论这个问题，但是 push() == 常数时间 和 get_min() == 常数时间，因此将最小值入栈和获取最小值的操作都是常数时间。常数时间指的是与堆栈大小相关的时间变化，在这种实现方式中，这些函数的执行时间不会随着堆栈的大小而改变。 - sberry

Answer 1

如果您只想存储所有推送元素中的单个最小值，则可以在O(1)的时间复杂度内且不使用O(n)的内存来完成此操作。

如果您想存储最小元素的历史记录，则除了使用辅助数据结构来保存它们之外，没有其他方法。在这种情况下，使用堆栈是最优的，因为您可以使用O(1)的时间进行推入/弹出，这是您正在使用的方法。

附注：您的代码包含一个微小的错误：

对于数组arr=[2, 2]， 在推送两次后，min_stack=[2]。

当您第一次弹出时，min_stack=[]，main_stack=[2]。 因此get_min()将返回None而不是2。

要修复它，请更改push_key:

 if len(min_stack) < 1 or min_stack[-1] >= key:

- trans1st0r

---

如果键是唯一的（正如作者在评论中所声称的那样），那么这不是一个错误。 - Scott Hunter

Answer 2

由于没有其他说明，我认为如果在64位系统上将推送到堆栈上的整数范围限制为32位，则可能包括一个解决方案。

我知道这些限制可能不适用，但我会把它留在这里，以防它引发其他想法。

注意 如果堆栈值不仅限于整数，则也可以类似地使用元组，其中x的推送将是(min_thus_far，x)的推送，例如。

arr = [10, 7, 15, 12, 3, 21]

main_stack = []

def get_min():
    if len(main_stack) == 0:
        return None
    return main_stack[-1] >> 32

def push(key):
    current_min = get_min()
    if current_min:
        if key < current_min:
            current_min = key
    else:
        current_min = key
    main_stack.append(key + (current_min << 32))

def pop():
    key = main_stack.pop()
    return key & 0xFFFFFFFF

for key in arr:
    push(key)

def print_state():
    print(", ".join(str(x & 0xFFFFFFFF) for x in main_stack))
    print("min: %d" %(get_min(),))

for _ in arr:
    print_state()
    print "popped:", pop()

OUTPUT:

10, 7, 15, 12, 3, 21
min: 3
popped: 21
10, 7, 15, 12, 3
min: 3
popped: 3
10, 7, 15, 12
min: 7
popped: 12
10, 7, 15
min: 7
popped: 15
10, 7
min: 7
popped: 7
10
min: 10
popped: 10

这里是一个元组版本：

arr = [10, 7, 15, 12, 3, 21]

main_stack = []

def get_min():
    if len(main_stack) == 0:
        return None
    return main_stack[-1][0]

def push(key):
    current_min = get_min()
    if current_min:
        if key < current_min:
            current_min = key
    else:
        current_min = key
    main_stack.append((current_min, key))

def pop():
    key = main_stack.pop()
    return key[1]

for key in arr:
    push(key)

def print_state():
    print(", ".join(str(x[1]) for x in main_stack))
    print("min: %d" %(get_min(),))

for _ in arr:
    print_state()
    print "popped:", pop()

- sberry

---

我认为我会主张这与原作者的解决方案在算法上没有区别。这是一种聪明的节省内存的方法，通过以稍微更紧凑的方式存储数据（基于列表中的元素只占用其可用内存的一半的假设），但它并不是一个不同的算法 :-) - mgilson

我同意，这个概念完全相同。答案在很大程度上受到了关于“利用整数键的算术属性”的询问的引导。尽管我认为维护单个堆栈比维护两个更容易，因为重复最小值的错误已经显示出来了。 - sberry

@sberry 这是一个聪明的技巧，绝对比我的解决方案更先进。 - anand