最小栈是在普通栈上多加一个能力：getMin() 要在 O(1) 时间返回当前栈里的最小值。
如果每次 getMin() 都从栈底扫到栈顶，当然能找到答案，但时间复杂度是 O(n)。题目要求所有操作都是常数时间，所以不能等到查询时再计算，必须在入栈时就把答案准备好。
核心思路：
栈的每一层，都应该知道”如果栈只剩到我这一层，当前最小值是谁”。
题目概览
| 来源 | 内容 |
|---|---|
class015 | GetMinStack |
题型： 带最小值查询的栈设计。
核心做法： 准备两个栈，一个存真实数据，一个同步存”当前层往下的最小值快照”。
易错点： data 和 min 必须同步进出；有重复最小值时不能丢掉上一层的最小状态；数组实现里 size 的读写顺序要统一。
155. 最小栈
实现一个 MinStack，支持：
push(int val)：压入元素pop()：弹出栈顶top()：返回栈顶元素getMin()：返回当前栈中的最小元素
题目保证 pop、top、getMin 都会在非空栈上调用。
LeetCode 调用过程如下：
给每一层存一份最小值快照
我们准备两个栈：
data：正常存数据min：和data一样高，每一层存”从栈底到当前层的最小值”
下面的栈按”左边是栈底，右边是栈顶”来看：
push(-2)data: [-2]min: [-2] 当前最小值是 -2
push(0)data: [-2, 0]min: [-2, -2] 0 不是最小值，但 min 仍然压入一层，记录"此时最小值仍是 -2"
push(-3)data: [-2, 0, -3]min: [-2, -2, -3] 当前最小值更新成 -3
getMin() → -3
pop()data: [-2, 0]min: [-2, -2] -3 被同步弹出，最小值自然回到 -2
top() → 0getMin() → -2重点在第二步：0 本身不是最小值，但 min 仍然压入一层 -2。因为这一层表达的是——当栈顶是 0 时，整个栈的最小值是 -2。
这就是”快照”的含义：每次 push 都把当时的最小值记录下来。以后 pop 时，真实数据弹一层，快照也弹一层，状态自然回到上一层。
整个设计只靠一个不变量撑住：
不变量
data和min永远等高。data的栈顶是当前元素，min的栈顶是当前最小值。
解法一：辅助栈
核心思路
data[i]：第i层真实压入的值min[i]：从栈底到第i层的最小值
每次 push(val) 时，真实值压入 data；同时把 val 和上一层最小值中更小的那个压入 min。每次 pop() 时，两个栈一起弹。因为栈顶元素离开后，它对应的最小值快照也应该一起失效。
代码实现
import java.util.Stack;
class MinStack {
private Stack<Integer> data; private Stack<Integer> min;
public MinStack() { data = new Stack<Integer>(); min = new Stack<Integer>(); }
public void push(int val) { data.push(val);
// min 和 data 同步压入一层，保存当前栈的最小值快照 if (min.isEmpty()) { min.push(val); } else { min.push(Math.min(val, min.peek())); } }
public void pop() { data.pop(); min.pop(); }
public int top() { return data.peek(); }
public int getMin() { return min.peek(); }}这份写法最舒服的地方在 pop()：不用判断弹出的元素是不是最小值。因为 min 不是”最小值出现记录表”，而是”每一层的最小值快照”，直接同步弹出即可。
变量角色
| 变量 | 作用 |
|---|---|
data | 真实栈，保存所有压入的元素 |
min | 辅助栈，min.peek() 永远是当前最小值 |
为什么不只在变小时压入 min
另一种常见写法是：只有当 val <= min.peek() 时，才把 val 压入 min。这当然也可以，但它有两个额外负担：
pop()时需要判断弹出的值是否等于min.peek()。- 遇到重复最小值时，必须用
<=，不能只用<。
例如：
push(2)push(2)pop()getMin()如果第二个 2 没有压进 min，第一次 pop() 就把唯一的 2 从 min 里弹掉，栈里明明还剩一个 2，getMin() 却已经没有正确答案了。
同步快照写法虽然多存了一些重复最小值，但胜在简单稳定：入栈一起入，出栈一起出。
解法二：数组模拟
如果想避开 Stack<Integer> 的对象开销，也可以用数组模拟两个栈。题目里总操作次数最多是 3 × 10^4，数组容量开到 30001 就足够。
class MinStack {
private static final int MAXN = 30001;
private int[] data; private int[] min; private int size;
public MinStack() { data = new int[MAXN]; min = new int[MAXN]; size = 0; }
public void push(int val) { data[size] = val; min[size] = size == 0 ? val : Math.min(val, min[size - 1]); size++; }
public void pop() { size--; }
public int top() { return data[size - 1]; }
public int getMin() { return min[size - 1]; }}size 表示”下一个可写位置”，所以代码顺序要保持一致：
push: 先写 data[size] 和 min[size]，再 size++pop: size--top: data[size - 1]min: min[size - 1]易错点
min 忘记同步弹出
错误写法：
public void pop() { data.pop(); // 漏掉 min.pop()}真实栈已经少了一层，但 min 还停在旧状态。之后 getMin() 可能返回一个已经被弹掉的值。
正确写法：
public void pop() { data.pop(); min.pop();}把 min 理解成”只存最小值”
同步快照写法里，min 不是只存新纪录：
data: [3, 5, 2, 4]min: [3, 2] ← 错误：只记录变小的值而应该是：
data: [3, 5, 2, 4]min: [3, 3, 2, 2] ← 正确：每层都有对应的最小值快照每个 data 位置都有对应的 min 位置，这样 pop 才能无脑同步。
数组版搞乱 size 的含义
数组写法里最怕一会儿把 size 当”当前最后一个元素位置”，一会儿又当”下一个可写位置”。选一个含义后就不要变。
复杂度
| 操作 | 时间复杂度 | 说明 |
|---|---|---|
push() | O(1) | 真实栈和辅助栈各压入一次 |
pop() | O(1) | 两个栈同步弹出一次 |
top() | O(1) | 直接看真实栈栈顶 |
getMin() | O(1) | 直接看辅助栈栈顶 |
空间复杂度：O(n)。除了真实数据外，还要为每一层额外保存一个最小值快照。
记法
最小栈不是在查询时找最小值，而是在入栈时就把答案存好。
真实栈存元素，辅助栈存每一层的最小值快照；进一起进，出一起出，辅助栈顶就是答案。
如果这篇文章对你有帮助，欢迎分享给更多人！
部分信息可能已经过时