题干与适用场景
实现一个支持 push(x)、pop()、top() 和 getMin() 的栈。所有操作都应为 O(1)，并说明空栈如何返回错误或特殊值。这道题适合通用编程、后端和基础库岗位，重点是把每个栈深度的最小值作为可维护不变量。
面试官考察点
不变量
辅助结构在深度 d 处保存主栈前 d 个元素的最小值，主栈和辅助栈始终等长。
重复最小值
新值等于当前最小值时也必须记录，否则 pop 一个重复值会错误地丢失最小值。
边界契约
空栈的 pop、top、getMin 必须有一致契约，例如抛出异常或返回 Result，不能静默返回未定义值。
复杂度
每个操作只访问栈顶，时间 O(1)，额外空间 O(n)。不能每次 getMin 扫描主栈。
回答前需要澄清的问题
- 空栈操作返回异常、可选值还是错误码？
- 输入是否可能包含重复值、负数和极大整数？
- 是否要求泛型比较器，还是只处理整数？
- 是否要返回最小值的索引或出现次数？
- 是否要求线程安全或无锁实现？
- 测试是单次操作，还是随机操作序列？
30 秒回答框架
“我使用两个等长栈：主栈保存所有值，辅助栈在每个深度保存截至该深度的最小值。push 时把 min(x, 当前最小值) 压入辅助栈；pop 同时弹出两栈；top 和 getMin 读取栈顶。因此所有操作都是 O(1)，额外空间 O(n)。重复最小值必须重复记录，空栈操作遵循明确契约。我会用慢速参考栈校验随机序列。”
分步骤深入解答
第一步：写出状态不变量
设主栈为 S，辅助栈为 M。对任意深度 d，M[d] 等于 S[0..d] 的最小元素，两栈长度相等。
第二步：设计 push
当前最小值存在时，辅助栈压入 min(x, M.top())；辅助栈为空时直接压入 x。
第三步：设计 pop 与查询
pop 同时弹出 S 与 M，top 读取 S.top()，getMin 读取 M.top()。不需要扫描。
第四步：处理重复值
依次 push 2、1、1 时，辅助栈为 2、1、1。pop 一次后仍保留 1。
第五步：错误契约与类型
空栈可抛出 EmptyStackError，或返回带错误状态的 Result。泛型实现应注入全序比较器。
第六步：复杂度与测试
四个操作均为 O(1)，额外空间 O(n)。随机测试维护普通列表作为 oracle，逐步比较 top、min、size 和错误结果。
~~~python class MinStack: def push(self, value): ... def pop(self): ... def top(self): ... def get_min(self): ... ~~~
高质量示范回答
“我会维护主栈 values 和辅助栈 mins。mins[i] 是 values[0..i] 的最小值，所以两栈长度相同。push 把 value 放入 values，并把 min(value, mins[-1]) 放入 mins；空栈时直接放 value。pop 同时弹出两栈，top 和 getMin 读取对应栈顶。
重复最小值必须重复压入，例如 2、1、1 的 mins 是 2、1、1；否则 pop 一个 1 后会错误返回 2。空栈使用明确错误契约。每个操作时间 O(1)，空间 O(n)。测试覆盖空栈、负数、重复最小值、交替操作和随机序列。”
常见错误
- 每次 getMin 扫描主栈，时间变成 O(n)。
- 只有遇到更小值才压辅助栈，无法处理重复最小值。
- pop 只弹主栈，导致两个结构长度不一致。
- 用一个全局 min 变量，pop 后无法恢复上一个最小值。
- 空栈静默返回 0，把合法输入 0 与错误混淆。
- 忽略负数或整数边界。
- 把均摊 O(1) 误说成每次严格 O(1)。
- 未定义比较器就声称支持任意对象。
追问及应对
追问一：能否只用一个栈？
可以把值和当时最小值组成一对压入同一栈，例如每个条目存 value 和 prefixMin。核心不变量不变，空间仍为 O(n)。
追问二：如何支持 getMax？
再维护一个保存前缀最大值的辅助栈，或把每个条目扩展为 value、min、max。时间仍为 O(1)，空间仍为 O(n)。
追问三：如何返回最小值出现次数？
辅助条目保存 min 和 count；相等时 count 加一，pop 时恢复前一条记录。
追问四：如何做线程安全？
用同一把互斥锁保护两栈的一次操作，不能分别加锁造成中间状态暴露。无锁实现需要原子复合状态和内存回收讨论。
追问五：如何证明正确？
用归纳法：空栈不变量成立；push 生成新前缀最小值；pop 恢复上一条记录。因此 getMin 总返回当前 S 的最小值。