程式面試：用單調堆疊解決循環陣列的下一個較大元素
面試官考察點
給定循環整數陣列，回傳每個元素順時針方向遇到的第一個嚴格較大元素；不存在時回傳 -1。陣列可能包含重複值、單調序列與全部相同的值。
約束與邊界
- 結果必須嚴格較大，等值不能出堆疊成為答案。
- 循環表示索引
i的候選順序為i+1到n-1，再回到0。 - 每個位置最多需要一個答案，不能因第二趟掃描覆蓋已確定結果。
- 目標是 O(n) 時間與 O(n) 空間。
30 秒回答框架
「我維護按值遞減的索引堆疊，堆疊中的元素尚未找到較大值。掃描虛擬的兩倍陣列：目前值嚴格大於堆疊頂端時持續彈出並填入答案；第一趟把所有位置放入堆疊，第二趟只為未解決位置提供環回候選。每個索引最多放入與彈出一次，複雜度 O(n)。 」
讓堆疊保存等待答案的位置
堆疊保存索引而不是值，方便寫回結果並保留重複值的相對位置。維持從堆疊底到頂端的非遞增值序；遇到較大值時，所有被它解決的索引都可以彈出。
把環回變成有限掃描
把存取位置寫成 i % n，讓 i 從 0 掃到 2n-2。第一次遇到同一索引時才放入堆疊；第二次遇到時只用來解決等待者，不再重複放入。這樣不必複製陣列，也不會無限迴圈。
嚴格大於與重複值
彈出條件必須是 nums[current] > nums[stackTop]。使用大於等於會讓相同值錯誤互相解決；使用小於則會破壞遞減堆疊不變量。沒有較大值的索引在掃描結束後保留 -1。
回答前需要釐清的問題
- 「下一個」是否嚴格較大？若改為大於或等於，彈出條件和重複值答案都會改變。
- 陣列是否允許為空？空陣列的回傳形式要先定義。
- 需要回傳值還是索引？若回傳距離或索引，結果結構與環回計算會不同。
分步驟深入解答
初始化結果為 -1，堆疊為空。對虛擬位置 i，令 index = i % n，讀取 value = nums[index]。先用 value 解決所有堆疊頂端較小的索引；當 i 小於 n 時把 index 放入堆疊，表示它仍等待右側較大值。第二趟不會再次放入，因此每個索引只加入一次。
result = [-1] * n
stack = []
for i in range(2 * n - 1):
index = i % n
while stack and nums[stack[-1]] < nums[index]:
result[stack.pop()] = nums[index]
if i < n:
stack.append(index)例如 [1,2,1] 的第三個 1 在環回時會看到 2，而 2 自己沒有嚴格較大的值。掃描結束後堆疊中的索引對應 -1，不需要額外清理。
高品質示範回答
「我用索引堆疊保存尚未找到答案的位置，並保持堆疊底到頂端的值非遞增。把陣列邏輯上掃描兩遍，每次用 i % n 讀取元素；目前值嚴格大於堆疊頂端時就彈出並寫答案。第一趟遇到位置才放入，第二趟只做環回匹配，避免重複放入。結果先填 -1，所以全相同陣列和沒有較大值的位置自然正確。每個索引最多放入與彈出一次，時間 O(n)，空間 O(n)。 」
常見錯誤
- 為了處理循環而複製三倍陣列，增加不必要的空間與邊界風險。
- 第二趟再次放入，導致同一索引被處理多次或答案被覆蓋。
- 使用大於等於處理重複值，讓相同元素被誤判為較大。
- 從右向左掃描卻沒有明確堆疊不變量，導致答案不是第一個較大值。
- 沒有先填
-1，結束後為堆疊索引補答案時出現未初始化值。
錯誤表現與修正
對 [1,1,1] 回傳非 -1 的值，表示等值條件錯誤；對 [1,2,1] 第三個位置回傳 -1，表示沒有進行環回掃描。修正時逐步列印堆疊索引和值，並斷言每次彈出前目前值嚴格較大。
生產化實作
將結果和堆疊使用足夠寬的索引型別；若輸入規模可能接近記憶體上限，避免複製陣列。需要回傳距離時，在彈出索引 j 時計算 (index - j + n) % n，並規定是否允許距離為零。
驗證清單
覆蓋空陣列、單元素、全相同、嚴格遞增、嚴格遞減、重複峰值與隨機陣列。小規模輸入用 O(n²) 參考實作逐位置向前查找，進行隨機對拍，驗證值、順序與 -1 邊界。
追問及應對
為什麼每個索引最多彈出一次？
索引一旦找到嚴格較大值就離開堆疊；之後更遠的元素不可能成為它的「第一個」較大值。每次放入一次、彈出一次，所以總彈出次數是 O(n)。
如果要求下一個大於或等於的元素呢？
把彈出條件改為小於或等於，並重新確認重複元素的順序。等值元素會互相解決，題目通常還要明確是否允許回傳自己在環上的再次出現。
如果陣列改為無限重複串流呢？
不能等待所有位置都有答案；需要給出有限觀察視窗或逾時策略。對固定陣列，最多掃描兩遍已經覆蓋每個位置後續的所有候選。
評分標準
- 狀態不變量：說明遞減堆疊保存等待答案的索引。
- 環回處理：使用兩趟或等價有限掃描，不複製或無限迴圈。
- 重複值邊界：嚴格使用大於條件，並保留無答案為
-1。 - 複雜度準確：O(n) 時間、O(n) 額外空間。
- 驗證充分：包含 O(n²) 參考實作和隨機、重複、單調序列測試。
合規檢查
確認堆疊不變量、環回邊界與複雜度結論在回答中保持一致。
面試作答要點
先講「堆疊中索引等待較大值」，再說明 i % n 的兩趟掃描、嚴格大於的彈出條件和只放入一次，最後給出攤還複雜度。
一句話總結
循環陣列的下一個較大元素可以透過兩趟索引掃描和單調遞減堆疊在線性時間完成，重複值與無答案位置由嚴格比較和 -1 初始化保證。