Monotonic Stack單調堆疊
維持遞增或遞減，找下一個更大／更小元素。
用在：股價分析、直方圖最大矩形、每日溫度
01為什麼需要它
對每一天問「之後第一個比今天高的價格在哪」。暴力做法每一天往後掃，O(n²)，十萬天就是一百億次。
為什麼用它從左到右掃，把「還沒找到答案的日子」放在堆疊裡。新的一天出現時，堆疊裡所有比它低的日子答案就是今天，一次全部彈出結算。每一天進出各一次，O(n)。
一排柱子，找面積最大的矩形。矩形的高由最矮的柱子決定，所以要知道每根柱子「左右第一根比它矮的在哪」。
為什麼用它這正是單調堆疊回答的問題。維持一個高度遞增的堆疊，彈出的那一刻同時知道左邊界（新的頂端）和右邊界（現在的位置）。
「被左右更高的東西夾住」「往右看第一個擋住視線的」，這類問題全部長得一樣。
為什麼用它它們都是「找左邊或右邊第一個更大／更小的元素」的變形。認出這個形狀，就知道要用單調堆疊。
看到這些關鍵字就想到它：下一個更大／更小、第一個比它高的、左右邊界、每個元素往右看、O(n²) 的雙層迴圈只在找「第一個滿足條件的」。
02核心概念
單調堆疊是一個堆疊，但多了一條規則：裡面的元素永遠保持遞增或遞減。要推入新元素前，先把所有會破壞單調性的元素彈出。彈出的那一刻，就是那個元素「找到答案」的時刻，因為新元素就是它右邊第一個比它大（或小）的。
以「下一個更大元素」為例。堆疊由底到頂遞減，存的是索引。新元素 x 來了：頂端比 x 小的元素，它們的答案就是 x，逐一彈出並記錄；然後把 x 推入。堆疊裡留下的是「還在等更大的」。每個索引恰好推入一次、彈出至多一次，所以整體 O(n)，把暴力的 O(n²) 壓掉一個 n。
方向與單調性的對應：找右邊第一個更大用遞減堆疊、從左往右掃；找右邊第一個更小用遞增堆疊；找左邊的第一個更大或更小，其實就是彈出時「新的頂端」，不用反過來掃。直方圖最大矩形一次拿到左右兩個邊界，就是這個性質。
等於的處理要想清楚。「嚴格更大」用 < 彈出，相等的留在堆疊；「大於等於」用 <=。直方圖那題加一個高度 0 的哨兵在尾端，讓所有柱子在最後都被彈出結算。
03演算法步驟
- 1確認問題是「對每個元素找某個方向第一個滿足大小條件的元素」。
- 2決定單調方向：找更大用遞減堆疊，找更小用遞增堆疊。堆疊裡存索引，才能算距離和取值。
- 3從左到右，對每個 i：
while stack and 條件(nums[stack[-1]], nums[i])，彈出頂端 j 並記錄ans[j]（答案是 i 或 nums[i]）。 - 4把 i 推入。若也需要「左邊第一個」，彈出 j 時的新頂端就是 j 的左邊界。
- 5掃完後堆疊裡剩下的元素沒有答案（設 −1 或 0）。需要全部結算時，在尾端加一個哨兵值。
04互動示範
每日溫度。黃色是還在堆疊裡等答案的日子，新的一天比頂端暖時，頂端被彈出並填上答案（綠色）。注意堆疊裡的溫度永遠由底到頂遞減。
05程式碼
每日溫度、通用的下一個更大元素，以及同時用到左右邊界的直方圖最大矩形。三段的骨架一模一樣，差在彈出條件和彈出時記什麼。
# 每日溫度（LeetCode 739）：每一天要等幾天才會更暖
# 堆疊存索引，對應的溫度由底到頂遞減
def daily_temperatures(temps):
ans = [0] * len(temps)
stack = [] # 還沒找到答案的日子
for i, t in enumerate(temps):
while stack and temps[stack[-1]] < t: # 今天比頂端暖
j = stack.pop()
ans[j] = i - j # 第 j 天的答案就是今天
stack.append(i)
return ans # 留在堆疊裡的是 0
# 下一個更大元素的通用版：回傳每個位置右邊第一個更大的值（沒有就 -1）
def next_greater(nums):
ans = [-1] * len(nums)
stack = []
for i, x in enumerate(nums):
while stack and nums[stack[-1]] < x:
ans[stack.pop()] = x
stack.append(i)
return ans
# 直方圖最大矩形（LeetCode 84）：對每根柱子找左右第一個比它矮的
def largest_rectangle(heights):
heights = heights + [0] # 哨兵，最後把所有柱子逼出來
stack = [] # 遞增堆疊
best = 0
for i, h in enumerate(heights):
while stack and heights[stack[-1]] >= h:
top = stack.pop()
left = stack[-1] if stack else -1 # 左邊第一個更矮的
width = i - left - 1 # 右邊第一個更矮的是 i
best = max(best, heights[top] * width)
stack.append(i)
return best06練習題
- LeetCode 739Daily TemperaturesMedium
- LeetCode 496Next Greater Element IEasy
- LeetCode 503Next Greater Element II（環狀：掃兩遍）Medium
- LeetCode 901Online Stock SpanMedium
- LeetCode 84Largest Rectangle in HistogramHard
- LeetCode 42Trapping Rain Water（單調堆疊版）Hard