「找每個元素的下一個更大值」——暴力 O(n²)，單調棧 O(n)。每個元素最多入棧一次、出棧一次，所以是線性。這個技巧看似冷門，但 LeetCode 上至少有七八題靠它。
先講結論
單調棧維護一個嚴格遞減（或遞增）的棧。遇到打破單調性的新元素時，不斷 pop 出棧頂，被 pop 的元素就找到了它的「下一個更大/更小值」。
下一個更大元素：模板
int[] nextGreater(int[] nums) {
int n = nums.length;
int[] result = new int[n];
Arrays.fill(result, -1);
Deque<Integer> stack = new ArrayDeque<>(); // 存索引
for (int i = 0; i < n; i++) {
while (!stack.isEmpty() && nums[stack.peek()] < nums[i]) {
result[stack.pop()] = nums[i];
}
stack.push(i);
}
return result;
}走一遍看看：
nums = [2, 1, 2, 4, 3]
i=0: stack=[0(2)]
i=1: 1<2, push → stack=[0(2), 1(1)]
i=2: 2>1, pop 1→result[1]=2 → stack=[0(2), 2(2)]
i=3: 4>2, pop→result[2]=4; 4>2, pop→result[0]=4 → stack=[3(4)]
i=4: 3<4, push → stack=[3(4), 4(3)]
result = [4, 2, 4, -1, -1]
棧裡最後剩下的元素，就是沒有「下一個更大值」的。
四種變體
| 目標 | 棧的單調性 |
|---|---|
| 下一個更大 | 遞減棧（棧頂最小） |
| 下一個更小 | 遞增棧（棧頂最大） |
| 上一個更大 | 遞減棧 |
| 上一個更小 | 遞增棧 |
差別只在比較方向和遍歷方向。模板骨架完全一樣。
經典應用
每日溫度
「還要等幾天才會更暖？」就是「下一個更大值的距離」。
temperatures = [73, 74, 75, 71, 69, 72, 76, 73]
result = [1, 1, 4, 2, 1, 1, 0, 0]
柱狀圖中最大矩形
heights = [2, 1, 5, 6, 2, 3]
██
████
████
████ ██
██ ████ ████
████████████
最大矩形 = 10（高度 5，寬度 2）
對每個柱子，找「左邊第一個更矮的」和「右邊第一個更矮的」，中間就是以這個高度能延伸的最大寬度。單調棧可以一次遍歷同時算出左右邊界。
接雨水
height = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]
██
██≈≈≈≈████≈≈██
██≈≈██≈≈████████████
████████████████████
接水量 = 6
這題可以用單調棧，也可以用雙指標。面試兩種解法都要會。
為什麼是 O(n)？
每個元素最多被 push 一次、pop 一次。所以雖然有 while 迴圈，整體還是 O(n)。這種「均攤分析」在面試中要能解釋清楚。
單調棧就像排隊：你前面的人比你矮，他就會被你「擠掉」（pop）。直到碰到一個比你高的人——他就是你的「下一個更大值」。至於被擠掉的人去了哪裡，那不是你的問題。