最小栈
Min Stack
本机进度仅保存在当前浏览器
题目描述
设计一个支持 push、pop、top 操作，并能在常数时间内检索到最小元素的栈。push、pop、top 和 getMin 都必须在 O(1) 时间内完成。
示例：依次 push(-2)、push(0)、push(-3)，getMin() 返回 -3；pop() 后 top() 返回 0，getMin() 返回 -2。
解题思路
- 每个元素入栈时，"当前时刻的最小值"也随之确定，且出栈后要恢复上一个最小值——这是典型的状态随栈帧存取。
- 辅助栈与主栈同步压入"到本层为止的最小值"，出栈时同步弹出，天然实现回滚。
- 空间优化：只在 x <= 当前最小值时才压辅助栈，出栈时若弹出的值等于最小值则同步弹出。
参考实现
查看参考实现Python · 建议先自行作答
class MinStack:
def __init__(self):
self.stack = []
self.mins = [] # mins[i] 为前 i+1 个元素的最小值
def push(self, val):
self.stack.append(val)
cur = self.mins[-1] if self.mins else val
self.mins.append(min(cur, val))
def pop(self):
self.stack.pop()
self.mins.pop()
def top(self):
return self.stack[-1]
def getMin(self):
return self.mins[-1]