LeetCode 面试题 03.02. 栈的最小值
目录
题目描述
题意分析
要设计一个栈，除了常规的
push、pop、top，还要支持getMin返回栈中当前最小元素。四个操作的语义都以"当前栈内容"为准：pop之后再问最小值，必须反映删除后的状态，不能返回历史最小值。
约束里最关键的信号是"要求所有操作都在常数时间内完成"。这句话直接否掉了两类朴素做法：
getMin时遍历栈是 $O(n)$，用堆或有序集合维护最小值是 $O(\log n)$。既然要 $O(1)$，就只能在push/pop的时刻顺手把答案算好存起来——也就是用空间换时间，把"最小值"变成随栈一起演化的状态。
边界上要覆盖：栈为空时不会被调用
pop/top/getMin（题目保证），但内部实现仍要保证push到空栈时最小值能被正确初始化；存在重复的最小值（比如连续压入两个-2，弹出一个后最小值仍应是-2）；元素可以是负数，所以不能拿 0 当"空"的哨兵。
解法：双栈（数据栈 + 最小栈）
核心思路
先看暴力：
getMin时把整个栈扫一遍取最小。这个做法push/pop都是 $O(1)$，但getMin是 $O(n)$，在"频繁查询最小值"的场景下就是瓶颈。第二个想法是用一个变量min缓存最小值，push时更新。这在只push不pop时完全正确，瓶颈出在pop：一旦弹出的正好是最小值，单个变量无法回答"次小值是多少"，因为这个信息已经被覆盖丢掉了。
关键观察由此而来：最小值不是一个标量，而是一个随栈深度变化的序列。栈是后进先出的，删除只发生在栈顶，所以"栈里前
k个元素的最小值"这个量对每个k都是确定且不会被后续push破坏的。既然它本身就是随栈深度单调演化的，就该用另一个栈把它一起存下来。
于是定义状态：
stack存所有元素，minStack存"最小值的历史"。不变量是：任意时刻minStack非空且minStack栈顶等于stack中所有元素的最小值；更强地，minStack从栈底到栈顶是一个非严格递减序列，其中每个值都对应stack里某个仍然存在的元素。
维持这个不变量的规则只有两条。
push(val)：当minStack为空或val <= minStack.peek()时，把val也压入minStack。这里必须用<=而不是<——如果最小值有重复，用<只会记录一份，后面弹掉一个就会把最小值信息整体丢掉。pop()：弹出数据栈顶v，若v == minStack.peek()则minStack也弹出一个。因为最小值重复了几次，minStack里就存了几份，一一对应地消耗，不会多弹也不会少弹。
解题步骤
- 构造函数里建立两个空栈。Java 用
ArrayDeque，Go 用切片。之所以不用Stack，是因为java.util.Stack继承自Vector，每个方法都带同步开销，是被淘汰的写法，面试里用Deque更专业。
push(val)：先无条件压数据栈，再按条件压最小栈。顺序上先压数据栈更安全，因为最小栈的判断依赖的是"压入之后stack里所有元素"的最小值。条件写成minStack.isEmpty() || val <= minStack.peek()：空栈时val本身就是唯一元素故必然是最小值；相等时也压，是为了给重复的最小值留够份数。
pop()：先弹数据栈拿到val，再判断是否同步弹最小栈。必须用弹出的值和minStack.peek()比较，而不是和stack新栈顶比较。判断相等就同步弹出，靠的正是"重复几次就存几份"的对应关系。
top()返回stack.peek()，getMin()返回minStack.peek()。两者都是直接读栈顶，不做任何计算，这就是 $O(1)$ 的来源。注意getMin绝不能去扫stack，否则前面所有的维护都白做了。
以操作序列
push(-2) → push(0) → push(-3) → getMin() → pop() → top() → getMin()走一遍：
push(-2)：stack = [-2]；minStack为空，压入，minStack = [-2]。push(0)：stack = [-2, 0]；0 <= -2不成立，不压，minStack = [-2]。push(-3)：stack = [-2, 0, -3]；-3 <= -2成立，压入，minStack = [-2, -3]。getMin()：返回minStack栈顶-3，正确。pop()：弹出stack顶得到-3，stack = [-2, 0]；-3 == minStack.peek()，故minStack也弹出，minStack = [-2]。top()：返回stack栈顶0。getMin()：返回minStack栈顶-2，正确——注意这一步恰好就是单变量缓存法会答错的地方，它会继续返回-3。再补一段重复最小值的走查
push(0) → push(1) → push(0) → getMin() → pop() → getMin()：三次 push 后stack = [0, 1, 0]，minStack = [0, 0]（第三个0因为0 <= 0成立而被压入）。getMin()返回0。pop()弹出0，与栈顶相等，minStack弹一份变成[0]。getMin()仍返回0，正确。若条件写成<，此时minStack会变成空栈，getMin直接崩溃。
代码实现
class MinStack {
private Deque<Integer> stack;
private Deque<Integer> minStack;
public MinStack() {
stack = new ArrayDeque<>();
minStack = new ArrayDeque<>();
}
public void push(int val) {
stack.push(val);
if (minStack.isEmpty() || val <= minStack.peek()) {
minStack.push(val);
}
}
public void pop() {
int val = stack.pop();
if (val == minStack.peek()) {
minStack.pop();
}
}
public int top() {
return stack.peek();
}
public int getMin() {
return minStack.peek();
}
}
type MinStack struct {
stack []int
minStack []int
}
func Constructor() MinStack {
return MinStack{}
}
func (s *MinStack) Push(val int) {
s.stack = append(s.stack, val)
if len(s.minStack) == 0 || val <= s.minStack[len(s.minStack)-1] {
s.minStack = append(s.minStack, val)
}
}
func (s *MinStack) Pop() {
top := s.stack[len(s.stack)-1]
s.stack = s.stack[:len(s.stack)-1]
if top == s.minStack[len(s.minStack)-1] {
s.minStack = s.minStack[:len(s.minStack)-1]
}
}
func (s *MinStack) Top() int {
return s.stack[len(s.stack)-1]
}
func (s *MinStack) GetMin() int {
return s.minStack[len(s.minStack)-1]
}
复杂度分析
- 时间复杂度：每个操作都是 $O(1)$。
push/pop只做常数次栈顶读写与一次比较，top/getMin只读栈顶，全程没有循环。- 空间复杂度：$O(n)$，
n为栈中元素个数。最坏情况是元素单调递减（如5, 4, 3, 2, 1），此时每个元素都会进入minStack，两个栈各存n个元素。
关键点总结
- "$O(1)$ 查询聚合值"的通用套路是把聚合值随结构一起维护。查询时算不出来，就在修改时算好；查询是读一个已经准备好的字段，这是所有"带 getMin/getMax/getMedian 的设计题"的共同骨架。
- 单个缓存变量能不能顶用，取决于删除操作是否可逆。只 push 不 pop 时一个
min变量足够；一旦允许删除，被覆盖的历史值就找不回来了，必须把"历史"整个存下来。判断标准是问自己："删掉当前极值后，我还能否恢复出新的极值？"- 重复元素的处理靠"存几份消耗几份"。把
push的条件从<放宽到<=，让重复的最小值在辅助栈里各占一格，pop时按值相等一一对消，就自然处理了多重最小值，不需要额外计数字段。- 面试视角：主动给出"辅助栈"和"存差值"两种方案并说明取舍。除了双栈，还可以在数据栈里存
val - min的差值，用 $O(1)$ 额外空间实现，但要处理 int 溢出（差值可能超出 int 范围，需要用 long）。面试里先给双栈保证写对，再补一句"如果面试官要求 $O(1)$ 额外空间，可以存差值，代价是要用 long 防溢出"，比只会一种更稳。- 设计题要先把不变量说清楚再动手。本题的不变量"
minStack栈顶恒等于当前最小值，且自底向上非严格递减"是所有代码行的依据；先说出来，写代码时每一行都能对照检查，也方便面试官跟上你的思路。
易错点总结
- 错误写法：
push的条件写成val < minStack.peek()→ 用例push(0), push(0), pop(), getMin()：第二个0因为0 < 0不成立而没进minStack，pop时0 == minStack.peek()成立又弹掉了唯一一份，minStack变空，getMin()抛出NoSuchElementException（Go 里是切片下标越界 panic）。- 错误写法：用单个
int min字段缓存最小值 → 用例push(-2), push(0), push(-3), pop(), getMin()：pop掉-3后min无法回退，仍返回-3，正确答案是-2。- 错误写法：
pop()里拿stack.peek()和minStack.peek()比较后再弹数据栈 → 若顺序写反成"先比较新栈顶"，用例push(1), push(2), pop()：比较的是即将成为栈顶的1而不是被弹出的2，1 == minStack.peek()成立导致最小栈被误弹，minStack变空，后续getMin()崩溃。- 错误写法：
getMin()里写return Collections.min(stack)→ 用例是任意长栈：单次查询退化成 $O(n)$，m次查询总代价 $O(nm)$，在3 * 10^4量级的操作序列上直接 TLE，同时也彻底废掉了minStack。- 错误写法：把
minStack初始化时先压一个Integer.MAX_VALUE当哨兵，但pop时不判空就弹 → 用例push(2147483647), pop(), getMin()：真实元素恰好等于哨兵值，pop会连哨兵一起弹掉，后续getMin崩溃。用哨兵就必须保证哨兵值不可能与真实数据相等，本题val可以取到 int 边界，哨兵不安全。- 错误写法：Java 里用
java.util.Stack并靠empty()判空，但pop时忘了它返回的是Integer对象 → 用例push(128), pop()：若把val == minStack.peek()写成两个Integer比较，超出-128..127缓存范围后比较的是引用地址，128 == 128返回false，最小栈该弹的没弹，之后getMin()永远偏小。Java 里务必让至少一侧是基本类型int，或改用equals。- 错误写法：Go 里
Pop()写成s.stack = s.stack[:len(s.stack)-1]但忘了先取出栈顶值 → 编译能过（若用s.stack[len(s.stack)-1]在截断之后取），但用例push(1), push(2), pop()：截断后再取栈顶得到的是1而不是被弹出的2，同样导致最小栈误弹。必须先取值后截断。- 错误写法：
Constructor()返回MinStack{}但方法接收者写成值类型func (s MinStack) Push(...)→ 用例push(1), top()：Push修改的是副本，主对象的切片始终为空，top()直接 panic。Go 里凡是修改自身字段的方法都必须用指针接收者。- 错误写法：把
minStack换成"每次 push 都压min(val, 当前最小)"但pop时不同步弹 → 用例push(3), push(1), pop(), getMin()：minStack变成[3, 1]且不弹，getMin()返回1，正确答案是3。这个变体本身是对的（每次都压，pop 时也每次都弹），错就错在两边不对称——压入策略和弹出策略必须成对设计。- 错误写法：
top()里写成stack.pop()→ 用例push(1), top(), top()：第一次top()返回1但把元素弹掉了，第二次top()直接崩溃。peek和pop一字之差，是设计题里最高频的手滑点。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 155. 最小栈 | 中等 | 完全同题，常被追问 $O(1)$ 额外空间的"存差值"写法 |
| 716. 最大栈 | 困难 | 多了 popMax 需要删除栈中间元素，双栈失效，要上双向链表加堆 |
| 剑指 Offer 30. 包含min函数的栈 | 简单 | 同一模型的剑指版本，接口名不同但不变量完全一致 |
| 剑指 Offer 59 - II. 队列的最大值 | 中等 | 删除发生在队首而非栈顶，辅助结构要换成单调双端队列 |
| 895. 最大频率栈 | 困难 | 极值定义在"出现频次"上，需要按频次分层的多个栈 |