「找每個元素的下一個更大值」——暴力 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]棧裡最後剩下的元素，就是沒有「下一個更大值」的。
四種變體
| 目標 | 棧的單調性 |
|---|---|
| 下一個更大 | 遞減棧（棧頂最小） |
| 下一個更小 | 遞增棧（棧頂最大） |
| 上一個更大 | 遞減棧 |
| 上一個更小 | 遞增棧 |
差別只在比較方向和遍歷方向。模板骨架完全一樣。
環形陣列：走兩圈
「下一個更大元素 II」（LeetCode 503）把陣列首尾接成環——最後一個元素的下一個更大值可以繞回開頭找。手法很土：把陣列走兩圈（i 從 0 跑到 2n，用 i % n 取值），第二圈只負責清算第一圈還沒配對到的，不再重複入棧。
int[] nextGreaterCircular(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 < 2 * n; i++) {
int cur = nums[i % n];
while (!stack.isEmpty() && nums[stack.peek()] < cur) {
result[stack.pop()] = cur;
}
if (i < n) stack.push(i); // 第二圈只清算、不入棧
}
return result;
}走兩圈就是給每個元素一次「往後繞整整一圈」的機會，總複雜度還是 O(n)。
經典應用
每日溫度
「還要等幾天才會更暖？」就是「下一個更大值的距離」。
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）。直到碰到一個比你高的人——他就是你的「下一個更大值」。至於被擠掉的人去了哪裡，那不是你的問題。
接下來往哪走
- Prefix Sum 前綴和 & Difference Array 差分陣列 — 下一篇：另一個「預處理換查詢」的面試高頻技巧
- Stack 堆疊 — 單調棧的底層結構，push/pop 的基礎在這裡
- Deque 雙端佇列 — 單調棧的兄弟「單調隊列」，滑動視窗最大值靠它