题目描述
设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。
示例:
输入：
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]
输出：
[null,null,null,null,-3,null,0,-2]
解释：
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); --> 返回 -3.
minStack.pop();
minStack.top(); --> 返回 0.
minStack.getMin(); --> 返回 -2.
提示：
pop、top 和 getMin 操作总是在 非空栈 上调用
解题思路
辅助栈
栈的先进后出的性质, 决定, 如果一个元素 a 在入栈时, 栈里有其它的元素 b, c, d, 那么无论这个栈在之后经历了什么操作, 只要 a 在栈中, b, c, d 就一定在栈中. 因为在 a 被弹出之前, b, c, d 不会被弹出.
因此，在操作过程中的任意一个时刻，只要栈顶的元素是 a，那么我们就可以确定栈里面现在的元素一定是 a, b, c, d.
那么，我们可以在每个元素 a 入栈时把当前栈的最小值 m 存储起来。在这之后无论何时，如果栈顶元素是 a，我们就可以直接返回存储的最小值 m.
过程:
设计一个数据结构, 使得每个元素 a 与其相应的最小值 m 时刻保持一一对应, 我们可以使用一个辅助栈, 与元素栈同步插入与删除, 用于存储与每个元素对应的最小值.
当一个元素要入栈时，我们取当前辅助栈的栈顶存储的最小值，与当前元素比较得出最小值，将这个最小值插入辅助栈中
当一个元素要出栈时，我们把辅助栈的栈顶元素也一并弹出
在任意一个时刻，栈内元素的最小值就存储在辅助栈的栈顶元素中
class MinStack:
def __init__(self):
"""
initialize your data structure here.
"""
self.num_stack = []
self.min_stack = [float('inf')] # 添加一个哨兵, 避免边界判断
def push(self, x: int) -> None:
self.num_stack.append(x)
self.min_stack.append(min(x, self.min_stack[-1]))
def pop(self) -> None:
self.num_stack.pop()
self.min_stack.pop()
def top(self) -> int:
return self.num_stack[-1]
def min(self) -> int:
return self.min_stack[-1]
在存储当前步最小值的辅助栈中放入一个极大值, 作为哨兵, 避免每一步判断边际的操作.
不使用额外的空间
结合以上的思路, 我们要在栈中存储的值, 就不能再是数值本身, 而是要存储当前数值与操作前最小值的差值.
如果这个差值小于0, 说明当前值是最小值. 在pop的过程中遇到, 说明将这个数pop出去后, 最小值就要更新, 要变大, 而新的最小值就是当前最小值减去这个差值
如果这个差值大于0, 说明最小的值还在栈中, 无需更新最小值
class MinStack:
def __init__(self):
"""
initialize your data structure here.
"""
self.stack = []
self.current_min = None
def push(self, x: int) -> None:
if len(self.stack) == 0:
self.stack.append(0)
self.current_min = x
else:
diff = x - self.current_min
self.stack.append(diff)
if diff < 0:
self.current_min = x
def pop(self) -> None:
diff = self.stack.pop()
if diff < 0:
self.current_min -= diff
def top(self) -> int:
return self.stack[-1] + self.current_min if self.stack[-1] >= 0 else self.current_min
def min(self) -> int:
return self.current_min
