题目
LC 155 最小栈：设计一个栈，支持
push、
pop、
top，并能在
O(1) 时间内取到栈内最小元素
getMin。
输入: push(-2), push(0), push(-3), getMin(), pop(), top(), getMin()
输出: getMin → -3
top → 0
getMin → -2
：只用两个栈，实现先进先出的队列，支持
push、
pop、
peek、
empty。
输入: push(1), push(2), push(3), pop(), peek(), pop()
输出: pop → 1, peek → 2, pop → 2
两题都是"给栈加约束"：栈天生只能看栈顶、只能后进先出，
155 却要求
知道整摞的最小值（而且是 pop 之后的旧最小值），
232 却要求
先进先出。一个要栈记住历史，一个要栈把顺序反过来。
一、LC 155 核心洞察：最小值是"历史"，必须按层存
先看约束卡在哪：
getMin 要
O(1)，可栈只能看到栈顶 —— 最小值埋在任意一层，每次现扫主栈是
O(n)，不合格。
真正难的不是"现在的最小值"，而是
pop 之后：
push(-2), push(0), push(-3) 之后
getMin 是
-3；
pop 掉
-3，
getMin 要回到
-2。
-2 是
过去的最小值 —— 栈弹掉一个元素，等于时间倒流，旧答案必须
本来就存着，不可能现场算出来还不扫描。
所以结论很直接：
最小值不是"当前状态"，是"历史"，要按层存。开一个
辅助栈 mins，与主栈同步：主栈每压入一个元素
x，辅助栈就记下"
x 入栈这一刻，全栈的最小值"。于是：
- 辅助栈顶恒等于全栈最小值（不变量）——
getMin 就是 O(1) 读辅助栈顶；
- pop 时两栈一起弹 —— 旧的最小值自动恢复，这就是"按层存"的意义。
class MinStack:
def __init__(self):
self.main = []
self.mins = []
def push(self, x):
self.main.append(x)
# 判据是 <=（相等也压），见 9.1
if not self.mins or x <= self.mins[-1]:
self.mins.append(x)
def pop(self):
x = self.main.pop()
if x == self.mins[-1]: # 弹的是当前最小值 → 同步弹
self.mins.pop()
return x
def top(self):
return self.main[-1]
def getMin(self):
return self.mins[-1] # O(1)：读历史栈顶
两个细节：
- 辅助栈不是每层都压：
push(0) 时 0 > -2，最小值没变，辅助栈留空档 —— 它存的是"变小的那一刻"，是主栈最小值的抽样历史；
- pop 的同步判据是
x == self.mins[-1]：只有弹掉的正好是当前最小值，辅助栈才跟着弹，否则最小值根本没动。
等价的省栈写法：每个栈帧直接存二元组
(值, 入栈时的最小值)，一个栈搞定，代价是每层都记（辅助栈只记变化点，通常更省）。两种写法面试都认，讲清"按层存"的思想即可。
二、LC 232 核心洞察：两次反转等于正序
栈是 LIFO，队列要 FIFO，方向正好相反。但"相反"这件事，
翻两次就是原样：
- 元素进
in 栈，被倒一次 —— 后来的压在先来的上面；
- 把
in 整摞翻进 out 栈，再倒一次 —— 最早来的反而沉到 out 顶。
out 顶就是队首。
pop /
peek 只动
out，方向就对了。
class MyQueue:
def __init__(self):
self.inn = []
self.out = []
def push(self, x):
self.inn.append(x) # O(1)，直接进
def _shift(self):
if not self.out: # 钉子一：out 空了才搬
while self.inn: # 钉子二：整摞翻
self.out.append(self.inn.pop())
def pop(self):
self._shift()
return self.out.pop()
def peek(self):
self._shift()
return self.out[-1]
def empty(self):
return not self.inn and not self.out
两条钉子缺一不可：
- 只在
out 空时搬运：out 里还有存货，说明有一批更老的元素还没消费完，此时把新元素混进去，out 顶就不是队首了（反例见 9.3）；
- 搬运必须整摞翻：
while 搬完。搬一半停手，out 里就是"新的压在旧的上面"，顺序当场坏掉。
均摊
O(1) 的账：每个元素一生至多三次栈操作 —— 进
in 一次、被搬一次、出
out 一次。
n 次队列操作总花费
O(n)。单次
pop 最坏
O(n)（恰好触发搬运），但那是把后面
n-1 次的账一次付清。
三、动画怎么看
最小栈动画（
algo-viz--lc155）：左列主栈、右列辅助栈，都从底向上画。
- 金框 = 本帧新压入；绿框 = 栈顶（可读位置）；橙虚线幽灵 = 本帧弹出的元素（停在原高度，看得见"刚弹掉的历史"）；
- push 帧若同步压了辅助栈，中间画出"同步压入"箭头；
push(0) 那帧没有箭头 —— 0 > -2，辅助栈留空档；
- pop 帧里
-3 两列同时变幽灵：它入栈时就是最小值，所以同步弹，-2 自动恢复成栈顶；
getMin 帧直接读辅助栈顶，横幅给出返回值 —— 全程不碰主栈。
双栈队列动画（
algo-viz--lc232）：左列
in 栈（进队），右列
out 栈（出队），底部一行是出队序列。
push 只进 in 顶；out 有存货时新元素乖乖排在后面，绝不搬运；- 第一次
pop 时 out 空了：先一帧"整摞翻！"，随后 3、2、1 逐个从 in 顶弹出（橙虚线）、压入 out 顶（金框）—— 每个元素一生就搬这一次；
- 翻完
out 顶是 1 —— 最早入队的元素，弹出记入底部出队行；
- 之后
push(4) 再 pop：out 里 3 还没消费完，4 不能插队，直接弹 3；out 弹空后下一才轮到 4。
四、完整推演表
LC 155（主栈、辅助栈都按"底 → 顶"写）：
注意帧 5：弹掉的
-3 恰好是辅助栈顶 —— 两栈同步弹，
-2 恢复。若帧 2 的
0 之后直接
pop，
0 不是辅助栈顶，辅助栈纹丝不动。
LC 232（
in /
out 按"底 → 顶"写）：
帧 11 → 12 是全表最值钱的两行：
out 还剩
3 时来了
4，正确做法是
先消费完 3 —— 若此时把
4 搬进
out，队首就错了（9.3 的反例）。
五、变体与同族题
5.1 LC 155 的变体
- 栈帧存
(值, 当前最小值)：一个栈、每层都记，思路完全一致，代码更短；辅助栈版只记"变小点"，空间通常更省；
- LC 716 最大栈：再加
peekMax / popMax。popMax 要弹中间的元素 —— 辅助栈救不了（它只回答"最大是谁"，不回答"最大在哪个位置"），得把栈顶临时挪开再挪回来；
O(1) 空间的差值编码：栈里存 x - 2*min 之类的差值、反推出最小值 —— 数学漂亮但极易写错，面试口头提一句即可，手写推荐辅助栈。
5.2 LC 232 的变体
- LC 225 用队列实现栈：反方向，代价放的位置也不同 —— 232 让
push 便宜（O(1)），把反转成本推迟到 pop；225 只能让 push 付账（入队后把前面一圈轮空，把新元素转到队尾），pop 反而 O(1)。两个方向不可能都便宜，这题考的就是谁付账；
- LC 844 比较含退格的字符串：
# 退格 = 栈顶弹出 —— 同款"用栈模拟带撤销的序列"；
- LC 641 设计循环双端队列：真正要双端时，双栈不够用了，上循环数组。
5.3 家族口诀
要顺序反过来 —— 再加一个栈（翻两次即正序）；要记住历史 —— 再加一列同步栈（每一刻的答案都按层存好）。 上一题 LC 20 的括号栈、LC 239 的单调队列，本质也都是这两句话。
六、Java 版
class MinStack {
Deque<Integer> main = new ArrayDeque();
Deque<Integer> mins = new ArrayDeque();
public void push(int x) {
main.push(x);
if (mins.isEmpty() || x <= mins.peek()) {
mins.push(x); // 判据 <=，相等也压
}
}
public void pop() {
if (main.pop().equals(mins.peek())) { // Integer 比较用 equals
mins.pop();
}
}
public int top() { return main.peek(); }
public int getMin() { return mins.peek(); }
}
class MyQueue {
Deque<Integer> in = new ArrayDeque();
Deque<Integer> out = new ArrayDeque();
public void push(int x) { in.push(x); }
private void shift() {
if (out.isEmpty()) { // out 空才搬
while (!in.isEmpty()) { // 整摞翻
out.push(in.pop());
}
}
}
public int pop() { shift(); return out.pop(); }
public int peek() { shift(); return out.peek(); }
public boolean empty() { return in.isEmpty() && out.isEmpty(); }
}
Java 的坑：
Deque 的
pop 返回
Integer，比较栈顶是否相等要用
equals（
== 在装箱缓存外会翻车，见 9.7）。
七、边界情况
八、复杂度
LC 155：
push /
pop /
top /
getMin 全
O(1)；空间
O(n) —— 辅助栈最坏（递减输入）与主栈等长，最好（递增输入）只有 1 个。本质是
用空间换"记住历史"。
LC 232：
push 最坏
O(1)；
pop /
peek 均摊 O(1)、单次最坏 O(n)（触发搬运）；空间
O(n)（两栈合计恰好存队列全部元素）。均摊账本：每元素一生至多 3 次栈操作（进
in、搬进
out、出
out），
n 次操作总花费
O(n)。
对照暴力做法：155 每次
getMin 扫全栈是
O(n)；232 每次
pop 把
in 翻进
out 再翻回来是
O(n) 单次、
O(n²) 总账 —— 双栈的"懒搬运"把总账压回
O(n)。
九、常见坑
9.1 辅助栈压入判据写成 <
push(2), push(2), pop 之后，
< 版只压过第一个
2 —— 弹掉第二个
2 时主栈还有
2，辅助栈却已经空了，
getMin 直接崩。
相等也是"这一刻的最小值"，必须
<= 再压一份。
9.2 pop 时无条件弹辅助栈
只有弹掉的值
等于当前最小值，辅助栈才跟着弹。
push(5), push(3), pop 弹掉
5 时辅助栈顶是
3，跟着弹就把还没发生的最小值提前扔了。先比较再弹。
9.3 out 没空就搬运
反例：
push(1), push(2), pop()（搬完得
out=[2]，返回 1），再
push(3)，此时若把
in 搬进
out，
out 变成
[2, 3]、顶是
3 —— 下次
pop 返回
3，可队首明明是
2。
搬运的前提是 out 已空，这条没有商量余地。
9.4 搬运搬一半
while (in 非空) out.push(in.pop()) 必须一口气搬完整摞。中途停手，
out 里出现"新的压在旧的上面"，FIFO 当场失效。
9.5 把"均摊 O(1)"说成"每次 O(1)"
单次
pop 触发搬运时就是
O(n)。面试要主动讲清口径：
n 次操作总花费 O(n)，均摊
O(1) —— 这是上一题 LC 239 同款账本。
9.6 155 里 pop 之后忘了"恢复过去"的设计初衷
有人只存"全局最小值"一个变量 ——
pop 掉最小值后，旧最小值无从恢复（除非重扫）。这正是"为什么必须按层存"的论证，答这题先答这句。
9.7 Java 比较栈顶用 ==
Deque.pop() 返回
Integer，
== 比较的是引用。装箱缓存只覆盖
-128..127，
1000 == 1000 可能为
false。用
equals（或先存进
int 变量拆箱）。
十、面试怎么答
- 155 先定性："最小值是历史，不是当前状态 —— pop 之后要回到过去，所以必须按层存。" 这一句比代码值钱；
- 报出不变量："辅助栈顶恒等于全栈最小值；它存的是最小值的抽样历史，判据
<=，相等也要压"；
- 232 先讲"两次反转"："进 in 倒一次，整摞翻进 out 再倒一次 —— out 顶就是队首"；
- 两条钉子："只在 out 空时搬、必须整摞搬"，并现场给 9.3 的反例证明第一条不可少；
- 主动报均摊账本："每元素一生至多搬一次，n 次操作 O(n) —— 单次最坏 O(n) 是提前付清"；
- 被问变体：225 是反方向（push 付账），716 的 popMax 辅助栈救不了（要弹中间），844 是同款栈模拟。
结语
这两题是栈家族的两块基石：
LC 155 教你"给栈加记忆"（同步辅助栈按层存历史），
LC 232 教你"给栈换方向"（双栈两次反转）。往后看，LC 20 的括号匹配是"只跟栈顶对话"，LC 239 的单调队列是"按支配关系淘汰"，LC 42 的单调栈是"按高度排队" —— 全部是这两招的排列组合。把"历史按层存、顺序翻两次"讲清楚，栈这一族题就有了共同的骨架。