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

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)    

在上述解决方案中，可以在 O(1) 中找到 min 值元素，但它使用了大小为 n 的辅助内存>.

有没有一种方法可以在不使用 n 大小的内存或常量内存的情况下，通过利用整数键的算术属性来完成。

Answer 1

如果您只想存储所有推送元素的单个最小值，则可以在 O(1) 中完成，而无需 O(n) 内存。

如果要存储 min 个元素的历史记录，那么除了使用辅助数据结构来保存它们之外别无他法。在这种情况下，使用堆栈是最佳选择，因为您可以在 O(1) 时间内推送/弹出，这是您正在使用的方法。

另外:您的代码包含一个小错误:

用你的数组 arr = [2, 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: