題幹與適用場景
實作 MaxStack：push(x) 壓入，pop() 刪除並回傳堆疊頂端，top() 查看頂端，peekMax() 查看最大值，popMax() 刪除並回傳最靠近頂端的最大值。重複最大值必須採後進先出；空堆疊行為先約定為錯誤或明確的空值。
公開的 LeetCode 題目和近期面試題記錄都採用這組介面。它與只維護前綴最小值的 Min Stack 不同：popMax 必須定位任意位置，並恢復剩餘元素的堆疊順序。
面試官考察點
- 能否先固定重複最大值的 tie-break 規則與空堆疊契約。
- 能否解釋為什麼只保存目前最大值的變數，在最大值刪除後無法快速恢復。
- 能否把「堆疊順序」和「按值找最大值」拆成兩個索引，並同步刪除同一節點。
- 能否區分輔助堆疊的攤銷
O(1)方案與平衡樹索引的O(log n)方案。
回答前需要釐清的問題
popMax必須是O(1)、攤銷O(1)，還是允許O(log n)？這是決定資料結構的核心約束。- 重複最大值要刪除最靠近堆疊頂端的一個，還是任意一個？不同規則會改變有序索引的定位方式。
- 是否要求穩定迭代器、並行呼叫或持久化？這些要求會影響節點生命週期和鎖策略。
- 值是可比較物件還是固定整數？固定整數可考慮桶或計數結構，泛型物件通常需要比較樹。
30 秒回答框架
「我把每個元素包成帶遞增序號的節點。雙向鏈結串列保持堆疊順序；有序索引按 (value, sequence) 排序，最大值位於索引末端。top 讀鏈結串列尾，peekMax 讀索引尾，popMax 從索引尾取出最大值後用節點指標從鏈結串列摘除。平衡樹方案的 push、pop、peekMax、popMax 都是 O(log n)，top 是 O(1)；如果只要求堆疊頂端操作和 peekMax 為常數，可用輔助最大值堆疊，但 popMax 需要搬移或重建，不能聲稱仍為 O(1)。」
分步深入解答
第一步：把堆疊順序和排序順序分開。
節點包含 value、單調遞增的 sequence、prev 和 next。鏈結串列尾端是堆疊頂端；有序索引的鍵為 (value, sequence)，相同值的元素按 sequence 較大者排在後面，因此索引尾端正好是最靠近頂端的最大值。
第二步：選擇可刪除的有序索引。
使用支援重複鍵的平衡樹、TreeMap 加有序節點集合，或「值到有序序號集合」的兩層索引。只保存 currentMax 不夠：刪除目前最大值後，必須知道下一個最大值和對應節點。
第三步：同步五個操作。
push：建立節點，接到鏈結串列尾，並插入有序索引。pop：取鏈結串列尾，從有序索引刪除同一節點，再摘除鏈結節點。top：回傳鏈結串列尾端的 value。peekMax：回傳有序索引尾節點的 value。popMax：取有序索引尾節點，按指標從鏈結串列刪除，再從索引刪除。
虛擬碼只展示關鍵不變量，實際樹 API 由語言決定：
node = orderedByValueAndSequence.last()
orderedByValueAndSequence.erase(node.key)
unlink(node.prev, node, node.next)
return node.value第四步：複雜度和替代方案。
平衡樹方案的五個操作中，top 是 O(1)，其餘涉及索引的操作是 O(log n)，空間為 O(n)。若允許 popMax 攤銷 O(n)，可用主堆疊加輔助最大值堆疊，把最大值變化記錄在每個深度；這更簡單，但不能滿足高頻任意位置刪除。
第五步：重複值、空堆疊和節點一致性。
sequence 同時解決重複值排序與 popMax 的 tie-break。空堆疊操作回傳統一錯誤。每個節點必須只在鏈結串列和索引各出現一次；刪除時先保存節點引用，再從兩個結構同時移除，避免索引懸掛。
第六步：測試順序與索引。
用慢速陣列作為參考模型。測試 [5,1,5] 連續兩次 popMax，應依序刪除頂端的 5 和底端的 5；涵蓋負數、全相等值、空堆疊、交替 push/pop、最大值在中間、重複刪除和隨機長序列。每次操作後同時驗證鏈結串列順序、索引大小和 peekMax 結果。
高品質示範回答
「我會用雙向鏈結串列保存堆疊順序，再用按 (value, sequence) 排序的平衡索引定位最大節點。sequence 單調遞增，所以重複最大值中序號最大者就是離堆疊頂端最近的一個。每個節點同時保存鏈結指標和索引鍵：pop 從鏈結串列尾端取節點，popMax 從索引尾端取節點，然後都從另一個結構刪除同一節點。如此 top 是 O(1)，其餘操作是 O(log n)，空間 O(n)。若面試官只要求 peekMax 而不要求任意位置刪除，我會改用輔助最大值堆疊，降低實作複雜度。」
常見錯誤
- 只保存一個目前最大值 → 刪除最大值後不知道下一個最大值 → 維護可查詢的有序索引。
- 把 popMax 當成 pop → 刪除錯誤位置，堆疊順序被改變 → 按索引找節點，再按鏈結指標摘除。
- 重複最大值不帶序號 → 無法證明刪除最靠近頂端的那個 → 鍵使用
(value, sequence)。 - 索引刪除後忘記鏈結節點 → 後續 top 讀到已刪除物件 → 兩個結構引用同一節點並原子更新。
- 把輔助堆疊方案寫成 popMax O(1) → 任意位置刪除通常要搬移元素或重建索引 → 明確寫出攤銷或最壞複雜度。
追問及應對
追問 1：能否讓所有操作都達到 O(1)？
若值是固定寬度整數，可以研究桶或專用整數優先結構，但複雜度會依賴值域寬度、記憶體和實作模型。對任意可比較物件，面試中應誠實給出 O(log n) 索引方案，不要把攤銷、期望和最壞界限混在一起。
追問 2：如何改成執行緒安全版本？
最簡單的契約是讓五個複合操作由同一把鎖保護，保證鏈結串列和有序索引不會暫時分叉。更高並行需要分片或不可變快照，但 popMax 涉及兩個結構的原子刪除，不能只分別加鎖後假設一致。
追問 3：如果只需要 peekMax，不需要 popMax 呢？
使用主堆疊加同長度的前綴最大值堆疊。push 同時記錄目前最大值，pop 同時彈出兩個堆疊，top 和 peekMax 讀取各自頂端，所有操作都是 O(1)；重複最大值必須重複記錄。