最小栈
Min Stack
设计一个栈，支持 push、pop、top 和 O(1) 的 getMin。
在力扣中练习题目描述
设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。
实现 MinStack 类:
MinStack()初始化堆栈对象。void push(int value)将元素value推入堆栈。void pop()删除堆栈顶部的元素。int top()获取堆栈顶部的元素。int getMin()获取堆栈中的最小元素。
示例 1:
输入： ["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.
提示：
-231 <= val <= 231 - 1pop、top和getMin操作总是在 非空栈 上调用push,pop,top, andgetMin最多被调用3 * 104次
解题思路
主解法
主栈 + 辅助最小值栈
辅助栈顶始终保存当前最小值
只用主栈无法 O(1) 取最小值；每次遍历一遍是 O(n)。用一个辅助栈 mins 记录“到这个位置为止的最小值”即可。
push 时，如果新值不大于当前最小值，就同时压入 mins。用 <= 而不是 <，是为了处理重复最小值：弹出其中一个时，另一个仍然保留在 mins 里。
分步图解
主栈保存所有元素，辅助栈保存“到这个位置为止的最小值”；两个栈同步维护。
data · 主栈
从栈顶进入与离开
mins · 每个位置对应的最小值
从栈顶进入与离开
pop 时，如果主栈弹出的值正好等于 mins 栈顶，mins 也弹出一个；否则 mins 不变。
分步图解
pop()：弹出 6；它不是最小值，mins 不变。
data · 主栈
6↑ 出栈
- 5
- 2← top
mins · 每个位置对应的最小值
从栈顶进入与离开
- 5
- 2← top
自拟操作里，6 比当前最小值 2 大，所以不进入 mins；1 进入后，getMin 返回 1；pop 掉 1 后，mins 栈顶回到 2。所有操作 O(1)，额外空间 O(n)。
时间 O(1)空间 O(n)
易错点
- push 用 < 而不是 <=：重复的最小值只存一份，弹出一个后 getMin 就错了。
- pop 只弹主栈：mins 没有同步回退。
- 用变量保存当前最小值：最小值被弹出后无法恢复次小值。
代码与演示
演示输入
push(5), push(2), push(6), getMin(), pop(), push(1), getMin(), pop(), top()主栈保存所有元素，辅助栈保存“到这个位置为止的最小值”；两个栈同步维护。
data · 主栈
从栈顶进入与离开
mins · 每个位置对应的最小值
从栈顶进入与离开
查看 C++ 代码
延伸阅读
- “每个位置对应的最小值”本质上是一个前缀最小值数组，用栈只是让它随 push/pop 同步伸缩。
- 同理可以维护前缀最大值、前缀和等可合并信息。