← 回首頁

單調棧(Monotone Stack)

生活裡常有這種問題:每天量氣溫,想知道「還要等幾天才會更熱」;或看著一排高矮不一的柱子,想找每根右邊第一個比它更高的。若每根都從頭比一次會很慢。單調棧的巧思像排一列「由高到矮的隊伍」:新來的人會把前面比他矮的一個個請出去,而被請出去的人此刻剛好找到了自己右邊第一個更高的對象——一趟掃描就把所有答案順手解完。下面你會看到棧內容如何隨掃描逐格變化,並對照三種經典題的解法。

單調棧是一個棧內元素始終保持單調(遞增或遞減)順序的棧:掃描陣列時,每當新元素破壞了單調性,就把棧內不符合的元素彈出(同時算出它們的答案),再把新元素推入。

1. 下一個更大元素(Next Greater Element)

維護一個由底到頂遞減的索引棧。掃描到 nums[i] 時,只要棧頂索引對應的值小於 nums[i], 就持續彈出並把該索引的 result 設為 nums[i];彈完後把 i 推入棧。掃描結束仍留在棧內的索引,代表右側沒有更大值,result 維持 -1。

陣列(逗號分隔,2–12 個整數,每個 1–99):
入棧次數:0 出棧次數:0
橘色(checking)為目前棧內索引;藍色外框為當前掃描位置 i;綠色為已解出 result 的索引。

棧內容(值(索引),底 → 頂)

結果 result(-1 表示尚未解出)

2. 最大矩形(Largest Rectangle in Histogram)

維護一個由底到頂遞增的索引棧(高度單調遞增)。掃描到高度 h 時,只要棧頂高度大於 h,就彈出並以「彈出高度 × 寬度」算出矩形面積、更新 maxArea; i 走到 n 時加入高度 0 的哨兵,清空棧內剩餘元素,確保所有柱子都被計算過。

高度(逗號分隔,2–12 個整數,每個 1–99):
入棧次數:0 出棧次數:0
淡出(半透明)的長條為目前矩形 range 之外的柱子;藍色外框為當前掃描位置 i。

棧內容(值(索引),底 → 頂)

結果 maxArea

3. 每日溫度(Daily Temperatures)

維護一個由底到頂遞減的索引棧(溫度單調遞減)。掃描到第 i 天時,只要棧頂索引對應的溫度低於 temps[i], 就彈出該索引 idx 並把 result[idx] = i - idx(等待天數);掃描結束仍留在棧內的天數,代表此後無更高溫,result 維持 0。

溫度(逗號分隔,2–12 個整數,每個 1–99,建議 60–100):
入棧次數:0 出棧次數:0
橘色(checking)為目前棧內索引;藍色外框為當前掃描位置 i;綠色為已解出等待天數的索引。

棧內容(值(索引),底 → 頂)

結果 result(等待天數,0 表示尚未解出)