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