本课时有配套视频讲解，购买后即可观看（永久有效）
单调栈
一、课上练习
编程练习
二、知识总结
✨ 核心思想
单调栈（Monotonic Stack）是一种特殊的栈结构，栈内元素始终保持单调递增或单调递减的顺序。每次入栈前，会弹出所有破坏单调性的元素。
单调栈的核心用途：高效地找到每个元素的下一个更大元素（Next Greater Element） 或 下一个更小元素。
关键性质：每个元素最多入栈一次、出栈一次，因此总时间复杂度为 O(n)。
✨ 算法原理
下一个更大元素（NGE）
给定数组 a，对每个元素 a[i]，找到它右边第一个比它大的元素。
暴力法：O(n²)，对每个元素向右扫描。
单调栈法：O(n)，维护一个单调递减栈（从栈底到栈顶递减）：
- 从左到右遍历数组
- 对于当前元素 a[i]，不断弹出栈顶，只要栈顶元素 < a[i]
- 被弹出的元素的"下一个更大元素"就是 a[i]
- 将 a[i] 入栈
下一个更大元素
1#include <bits/stdc++.h>
2using namespace std;
3
4int main() {
5 int n;
6 scanf("%d", &n);
7 vector<int> a(n), nge(n, -1); // nge[i] = -1 表示没有更大的
8
9 for (int i = 0; i < n; i++) scanf("%d", &a[i]);
10
11 stack<int> stk; // 存储下标，维护单调递减栈
12
13 for (int i = 0; i < n; i++) {
14 // 当前元素比栈顶大，说明栈顶找到了它的 NGE
15 while (!stk.empty() && a[stk.top()] < a[i]) {
16 nge[stk.top()] = i; // 或者 nge[stk.top()] = a[i]
17 stk.pop();
18 }
19 stk.push(i);
20 }
21
22 // 栈中剩余的元素没有 NGE
23 for (int i = 0; i < n; i++)
24 printf("%d ", nge[i] == -1 ? -1 : a[nge[i]]);
25
26 return 0;
27}✨ 执行示例
以数组 [2, 1, 4, 3, 5] 为例：
| 步骤 | i | a[i] | 操作 | 栈（下标→值） | 确定的 NGE |
|---|---|---|---|---|---|
| 1 | 0 | 2 | 栈空，直接入栈 | [0→2] | |
| 2 | 1 | 1 | 1 < 2，直接入栈 | [0→2, 1→1] | |
| 3 | 2 | 4 | 4 > 1，弹出 1；4 > 2，弹出 2 | [2→4] | nge[1]=4, nge[0]=4 |
| 4 | 3 | 3 | 3 < 4，直接入栈 | [2→4, 3→3] | |
| 5 | 4 | 5 | 5 > 3，弹出 3；5 > 4，弹出 4 | [4→5] | nge[3]=5, nge[2]=5 |
最终结果：
| 元素 | 2 | 1 | 4 | 3 | 5 |
|---|---|---|---|---|---|
| NGE | 4 | 4 | 5 | 5 | -1 |
✨ 经典问题：柱状图中最大矩形
问题：给定 n 个非负整数，表示柱状图中各柱子的高度，求能勾勒出的最大矩形面积。
思路：对于每根柱子，找到它左边第一个比它矮的柱子和右边第一个比它矮的柱子，这两个位置之间就是以当前柱子高度为矩形高的最大宽度。
柱状图中最大矩形
1#include <bits/stdc++.h>
2using namespace std;
3
4int main() {
5 int n;
6 scanf("%d", &n);
7 vector<int> h(n);
8 for (int i = 0; i < n; i++) scanf("%d", &h[i]);
9
10 vector<int> left(n), right(n);
11 stack<int> stk;
12
13 // 找左边第一个比 h[i] 小的位置（单调递增栈，从左往右）
14 for (int i = 0; i < n; i++) {
15 while (!stk.empty() && h[stk.top()] >= h[i])
16 stk.pop();
17 left[i] = stk.empty() ? -1 : stk.top();
18 stk.push(i);
19 }
20
21 // 清空栈
22 while (!stk.empty()) stk.pop();
23
24 // 找右边第一个比 h[i] 小的位置（单调递增栈，从右往左）
25 for (int i = n - 1; i >= 0; i--) {
26 while (!stk.empty() && h[stk.top()] >= h[i])
27 stk.pop();
28 right[i] = stk.empty() ? n : stk.top();
29 stk.push(i);
30 }
31
32 // 计算最大面积
33 long long ans = 0;
34 for (int i = 0; i < n; i++) {
35 long long area = (long long)h[i] * (right[i] - left[i] - 1);
36 ans = max(ans, area);
37 }
38
39 printf("%lld\n", ans);
40 return 0;
41}✨ 执行示例：柱状图
以 h = [2, 1, 5, 6, 2, 3] 为例：
| i | h[i] | left[i] | right[i] | 宽度 | 面积 |
|---|---|---|---|---|---|
| 0 | 2 | -1 | 1 | 1 | 2 |
| 1 | 1 | -1 | 6 | 6 | 6 |
| 2 | 5 | 1 | 4 | 2 | 10 |
| 3 | 6 | 2 | 4 | 1 | 6 |
| 4 | 2 | 1 | 6 | 4 | 8 |
| 5 | 3 | 4 | 6 | 1 | 3 |
最大面积 = 10（以 h[2]=5 为高，宽度为 right[2]-left[2]-1 = 4-1-1 = 2）
✨ 单调栈的变体
从右往左扫描
有时从右往左扫描更方便：
下一个更大元素（从右往左）
1// 从右往左遍历，维护单调递减栈
2for (int i = n - 1; i >= 0; i--) {
3 while (!stk.empty() && a[stk.top()] <= a[i])
4 stk.pop();
5 nge[i] = stk.empty() ? -1 : stk.top();
6 stk.push(i);
7}环形数组
如果数组是环形的（最后一个元素的下一个是第一个元素），可以遍历两圈：
环形数组的 NGE
1int n;
2// 遍历 2n 次
3for (int i = 2 * n - 1; i >= 0; i--) {
4 while (!stk.empty() && a[stk.top() % n] <= a[i % n])
5 stk.pop();
6 nge[i % n] = stk.empty() ? -1 : a[stk.top() % n];
7 stk.push(i);
8}✨ 解题步骤详解
遇到以下关键词时，考虑单调栈：
- "下一个更大/更小元素" → 经典单调栈
- "左边/右边第一个更大/更小" → 单调栈，注意方向
- "柱状图矩形" → 找左右两边第一个更小的
- "股票问题"中的"跨度" → 找左边第一个更大的
- "接雨水"问题 → 单调栈或双指针
选择单调递增还是递减：
- 找"下一个更大"→ 维护递减栈（遇到更大的就弹出）
- 找"下一个更小"→ 维护递增栈（遇到更小的就弹出）
✨ 常见错误
- 单调性方向搞反：找更大元素用递减栈，找更小元素用递增栈，容易混淆
- 存值还是存下标：大多数情况下存下标更好，因为下标既能算距离又能取值
- 相等元素的处理：
a[stk.top()] < a[i]和a[stk.top()] <= a[i]结果不同，需根据题意选择 - 栈中剩余元素未处理：遍历结束后栈中可能还有元素，它们没有找到对应的更大/更小值
- 柱状图问题边界：左边界默认 -1，右边界默认 n，忘记这些哨兵值会导致宽度计算错误
✨ 算法评价
| 特性 | 单调栈 |
|---|---|
| 时间复杂度 | O(n)，每个元素入栈出栈各一次 |
| 空间复杂度 | O(n) |
| 适用问题 | NGE/NSE、柱状图矩形、接雨水、股票跨度 |
| 核心优势 | 将"暴力枚举右边所有元素"优化为均摊 O(1) |
单调栈是竞赛中非常实用的工具。它的代码简短，但理解其原理需要一定的思考。建议多画图模拟栈的变化过程，加深理解。