題幹與適用場景
實作一个支援 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 的最小值。