最小栈 · 双栈同步版

栈 · 辅助栈

用 dataStack 存真实元素， minStack 存每一层前缀最小值。两栈等长、同步 push/pop，getMin 读 minStack 栈顶 O(1)。

当前用例

push 3,1,2 · getMin · 两次 pop

主线 10 步：看清 pop 后 min 如何沿 minStack 恢复

第一次 pop 只弹出 2，getMin 仍是 1；第二次 pop 弹出 1 后 min 才回到 3

目标反例双栈逐步执行总结Step 1 / 10

目标题目目标 · 四个操作都要 O(1)1/10

当前发生了什么

题目目标 · 四个操作都要 O(1)

设计 MinStack：push、pop、top、getMin 均摊 O(1)。不能每次 getMin 都扫描整个栈（那是 O(n)），也不能 pop 后再遍历找回最小值。

机器状态

dataStack: []
minStack: []
栈深（应相等）: 0 / 0
getMin: —
最近 pop: —
最近 push: —

为什么正确

面试常考「辅助结构」：用额外 O(n) 空间换 O(1) 查询，且 pop 后仍要知道新的最小值。

设计 MinStack：push、pop、top、getMin 均摊 O(1)。不能每次 getMin 都扫描整个栈（那是 O(n)），也不能 pop 后再遍历找回最小值。…

执行轨迹

目标：push / pop / top / getMin 均 O(1)

Go · 双栈同步版

1type MinStack struct {
2    data []int // 真实元素
3    mins []int // 每层前缀最小值，与 data 等长
4}
5 
6func (s *MinStack) Push(val int) {
7    s.data = append(s.data, val)
8    if len(s.mins) == 0 {
9        s.mins = append(s.mins, val)
10    } else {
11        top := s.mins[len(s.mins)-1]
12        s.mins = append(s.mins, min(val, top))
13    }
14}
15 
16func (s *MinStack) Pop() {
17    s.data = s.data[:len(s.data)-1]
18    s.mins = s.mins[:len(s.mins)-1] // 与 data 同步弹出
19}
20 
21func (s *MinStack) Top() int {
22    return s.data[len(s.data)-1]
23}
24 
25func (s *MinStack) GetMin() int {
26    return s.mins[len(s.mins)-1] // O(1) 读栈顶
27}

不变量

dataStack 和 minStack 长度始终相同；minStack[i] 表示 dataStack[0..i] 的最小值；因此 minStack 栈顶永远是当前栈最小值。

步骤时间线

面试回答

我用两个栈。dataStack 存真实元素，minStack 存每一层对应的历史最小值。push 时压入 min(x, 当前 min)，pop 时两个栈同步弹出，top 看 dataStack 栈顶，getMin 看 minStack 栈顶。四个操作 O(1)，空间 O(n)。

常见错误

pop 时只弹 dataStack 忘记同步 pop minStack；或误用压缩版却在 pop 时漏弹 minStack。

易错表达：「pop 一次后 min 自动回到 3」—— 只有弹出最小元素 1 之后才会回到 3。