如果我想在堆栈中找到一个最小元素(整数键),在恒定时间内,那么它可以如下完成:
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
大小的内存或常数内存的情况下,通过利用整数键的算术特性来完成。
如果只想存储所有推送元素的单个最小值,则可以在没有O(n)
内存的O(1)
中执行此操作。
如果您想存储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:
由于没有另行说明,我想如果在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()
输出:
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()