入棧次數:0
出棧次數:0
橘色(checking)為目前棧內索引;藍色外框為當前掃描位置 i;綠色為已解出 result 的索引。
生活裡常有這種問題:每天量氣溫,想知道「還要等幾天才會更熱」;或看著一排高矮不一的柱子,想找每根右邊第一個比它更高的。若每根都從頭比一次會很慢。單調棧的巧思像排一列「由高到矮的隊伍」:新來的人會把前面比他矮的一個個請出去,而被請出去的人此刻剛好找到了自己右邊第一個更高的對象——一趟掃描就把所有答案順手解完。下面你會看到棧內容如何隨掃描逐格變化,並對照三種經典題的解法。
單調棧是一個棧內元素始終保持單調(遞增或遞減)順序的棧:掃描陣列時,每當新元素破壞了單調性,就把棧內不符合的元素彈出(同時算出它們的答案),再把新元素推入。
維護一個由底到頂遞減的索引棧。掃描到 nums[i] 時,只要棧頂索引對應的值小於 nums[i],
就持續彈出並把該索引的 result 設為 nums[i];彈完後把 i 推入棧。掃描結束仍留在棧內的索引,代表右側沒有更大值,result 維持 -1。
維護一個由底到頂遞增的索引棧(高度單調遞增)。掃描到高度 h 時,只要棧頂高度大於 h,就彈出並以「彈出高度 × 寬度」算出矩形面積、更新 maxArea; i 走到 n 時加入高度 0 的哨兵,清空棧內剩餘元素,確保所有柱子都被計算過。
維護一個由底到頂遞減的索引棧(溫度單調遞減)。掃描到第 i 天時,只要棧頂索引對應的溫度低於 temps[i],
就彈出該索引 idx 並把 result[idx] = i - idx(等待天數);掃描結束仍留在棧內的天數,代表此後無更高溫,result 維持 0。