第 3.5 章：单调栈与单调队列
📝 前置条件： 确保你熟悉双指针/滑动窗口（第 3.4 章）和基本的栈/队列操作（第 3.1 章）。本章直接建立在这些技术之上。
单调栈和单调队列是优雅的工具，能在 O(N) 时间内解决「最近更大/更小元素」和「滑动窗口极值」问题——而朴素做法需要 O(N²)。
3.5.1 单调栈：下一个更大元素
题目： 给定 N 个整数的数组 A，对每个元素 A[i]，找下一个更大元素（NGE）：i 右侧第一个大于 A[i] 的元素的下标。若不存在，输出 -1。
朴素做法： O(N²) —— 对每个 i，向右扫描直到找到更大的元素。
单调栈做法： O(N) —— 维护一个从底到顶始终递减的栈。压入新元素时，先弹出所有更小的元素（它们刚找到了自己的 NGE！）。
💡 核心思路： 栈中存放还未找到 NGE 的元素的下标。当 A[i] 到来时，栈中所有小于 A[i] 的元素都找到了 NGE（就是 i！）。弹出它们并记录答案。
单调栈状态变化——对 A = [2, 1, 5, 6, 2, 3] 逐步追踪：
📄 
数组 A：[2, 1, 5, 6, 2, 3]
下标： 0 1 2 3 4 5
处理 i=0 (A[0]=2)：栈为空 → 压入 0
栈：[0] // 栈存放未解决元素的下标
处理 i=1 (A[1]=1)：A[1]=1 < A[0]=2 → 直接压入
栈：[0, 1]
处理 i=2 (A[2]=5)：
A[2]=5 > A[1]=1 → 弹出 1，NGE[1] = 2 (A[2]=5 是 A[1] 的下一个更大元素)
A[2]=5 > A[0]=2 → 弹出 0，NGE[0] = 2 (A[2]=5 是 A[0] 的下一个更大元素)
栈为空 → 压入 2
栈：[2]
处理 i=3 (A[3]=6)：
A[3]=6 > A[2]=5 → 弹出 2，NGE[2] = 3
压入 3
栈：[3]
处理 i=4 (A[4]=2)：A[4]=2 < A[3]=6 → 直接压入
栈：[3, 4]
处理 i=5 (A[5]=3)：
A[5]=3 > A[4]=2 → 弹出 4，NGE[4] = 5
A[5]=3 < A[3]=6 → 停止，压入 5
栈：[3, 5]
结束：栈中剩余 [3, 5] → NGE[3] = NGE[5] = -1（右侧无更大元素）
结果：NGE = [2, 2, 3, -1, 5, -1]
验证：
A[0]=2，下一个更大是 A[2]=5 ✓
A[1]=1，下一个更大是 A[2]=5 ✓
A[2]=5，下一个更大是 A[3]=6 ✓
A[3]=6，无更大 → -1 ✓
完整实现
📄 查看代码：完整实现
// 用单调栈求下一个更大元素 — O(N)
#include <bits/stdc++.h>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n;
cin >> n;
vector<int> A(n);
for (int& x : A) cin >> x;
vector<int> nge(n, -1); // nge[i] = 下一个更大元素的下标，不存在则为 -1
stack<int> st; // 单调递减栈（存下标）
for (int i = 0; i < n; i++) {
// 当栈顶元素小于 A[i] 时
// → 当前元素 A[i] 是那些元素的 NGE
while (!st.empty() && A[st.top()] < A[i]) {
nge[st.top()] = i; // ← 关键：记录栈顶的 NGE
st.pop();
}
st.push(i); // 压入当前下标（尚未解决）
}
// 栈中剩余元素没有 NGE → 已初始化为 -1
for (int i = 0; i < n; i++) {
cout << nge[i];
if (i < n - 1) cout << " ";
}
cout << "\n";
return 0;
}
复杂度分析：
- 每个元素恰好被压入一次，最多被弹出一次
- 总操作：O(2N) = O(N)
- 空间：O(N)（栈）
⚠️ 常见错误： 在栈中存值而非下标。始终存下标——你需要知道在数组的哪个位置记录答案。
3.5.2 变体：上一个更小、上一个更大
通过改变比较方向和遍历方向，可以得到四个相关问题：
| 问题 | 栈类型 | 方向 | 使用场景 |
|---|---|---|---|
| 下一个更大元素（NGE） | 递减栈 | 从左到右 | 股票价格问题 |
| 下一个更小元素（NSE） | 递增栈 | 从左到右 | 直方图问题 |
| 上一个更大元素（PGE） | 递减栈 | 从右到左 | 区间问题 |
| 上一个更小元素（PSE） | 递增栈 | 从右到左 | 左侧最近更小元素 |
上一个更小元素的模板：
📄 C++ 完整代码
// 上一个更小元素：对每个 i，找最近的 j < i 使得 A[j] < A[i]
vector<int> pse(n, -1); // pse[i] = 上一个更小元素的下标，不存在则为 -1
stack<int> st;
for (int i = 0; i < n; i++) {
while (!st.empty() && A[st.top()] >= A[i]) {
st.pop(); // 弹出 >= A[i] 的元素（它们不是「上一个更小」）
}
pse[i] = st.empty() ? -1 : st.top(); // 栈顶就是上一个更小
st.push(i);
}
3.5.3 USACO 应用：直方图中的最大矩形
题目： 给定高度数组 H[0..N-1]，找能放入直方图内的最大矩形面积。
核心思路： 对每根柱子 i，以 H[i] 为高度的最大矩形向左右延伸，直到遇到更矮的柱子。用单调栈求每个 i 的：
left[i]= 上一个更小元素的下标right[i]= 下一个更小元素的下标
每根柱子的左右边界——H = [2, 1, 5, 6, 2, 3]：
💡 公式：
宽度 = right[i] - left[i] - 1，面积 = H[i] × 宽度。左边界 = 上一个更小元素的下标；右边界 = 下一个更小元素的下标。
📄 C++ 完整代码
// 直方图中最大矩形 — O(N)
#include <bits/stdc++.h>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n;
cin >> n;
vector<int> H(n);
for (int& h : H) cin >> h;
vector<int> left(n), right(n);
stack<int> st;
// 上一个更小（左边界）
for (int i = 0; i < n; i++) {
while (!st.empty() && H[st.top()] >= H[i]) st.pop();
left[i] = st.empty() ? -1 : st.top(); // 矩形起点前的下标
st.push(i);
}
while (!st.empty()) st.pop();
// 下一个更小（右边界）
for (int i = n - 1; i >= 0; i--) {
while (!st.empty() && H[st.top()] >= H[i]) st.pop();
right[i] = st.empty() ? n : st.top(); // 矩形终点后的下标
st.push(i);
}
// 计算最大面积
long long maxArea = 0;
for (int i = 0; i < n; i++) {
long long width = right[i] - left[i] - 1; // 矩形宽度
long long area = (long long)H[i] * width;
maxArea = max(maxArea, area);
}
cout << maxArea << "\n";
return 0;
}
对 H = [2, 1, 5, 6, 2, 3] 的追踪：
left = [-1, -1, 1, 2, 1, 4] （上一个更小的下标，-1 = 无）
right = [1, 6, 4, 4, 6, 6] （下一个更小的下标，n=6 = 无）
宽度： 1-(-1)-1=1, 6-(-1)-1=6, 4-1-1=2, 4-2-1=1, 6-1-1=4, 6-4-1=1
面积： 2×1=2, 1×6=6, 5×2=10, 6×1=6, 2×4=8, 3×1=3
最大面积 = 10
i=2：H[2]=5，left[2]=1，right[2]=4，宽度=4-1-1=2，面积=5×2=10 ✓
（下标 2 和 3 的柱子高度都 ≥ 5，所以高度为 5 的矩形跨度为 2）
📌 学习建议： 提交前始终用样例输入手动追踪算法。下标边界的细微差一错误是单调栈问题最常见的 bug。
3.5.4 单调双端队列：滑动窗口最大值
题目： 给定 N 个整数的数组 A 和窗口大小 K，找每个大小为 K 的窗口从左向右滑动时的最大值，输出 N-K+1 个值。
朴素做法： O(NK) —— 对每个窗口扫描求最大值。
单调双端队列做法： O(N) —— 维护一个递减双端队列（队首 = 当前窗口最大值）。
💡 核心思路： 我们想要滑动窗口的最大值。维护一个下标的双端队列，使得：
- 双端队列中的值递减（队首始终是最大值）
- 双端队列只包含当前窗口内的下标
当新元素到来时：
- 从队尾移除所有更小的元素（只要这个新元素在窗口中，它们就不可能是最大值）
- 若队首已超出当前窗口则移除
逐步追踪
📄 查看代码：逐步追踪
数组 A：[1, 3, -1, -3, 5, 3, 6, 7]，K = 3
窗口 [1,3,-1]：最大 = 3
窗口 [3,-1,-3]：最大 = 3
窗口 [-1,-3,5]：最大 = 5
窗口 [-3,5,3]：最大 = 5
窗口 [5,3,6]：最大 = 6
窗口 [3,6,7]：最大 = 7
i=0, A[0]=1：双端队列=[0]
i=1, A[1]=3：3>1 → 弹出 0；双端队列=[1]
i=2, A[2]=-1：-1<3 → 压入；双端队列=[1,2]；窗口 [0..2]：最大=A[1]=3 ✓
i=3, A[3]=-3：-3<-1 → 压入；双端队列=[1,2,3]；窗口 [1..3]：队首=1 仍在窗口，最大=A[1]=3 ✓
i=4, A[4]=5：5>-3→弹出 3；5>-1→弹出 2；5>3→弹出 1；双端队列=[4]；窗口 [2..4]：最大=A[4]=5 ✓
i=5, A[5]=3：3<5→压入；双端队列=[4,5]；窗口 [3..5]：队首=4 在窗口，最大=A[4]=5 ✓
i=6, A[6]=6：6>3→弹出 5；6>5→弹出 4；双端队列=[6]；窗口 [4..6]：最大=A[6]=6 ✓
i=7, A[7]=7：7>6→弹出 6；双端队列=[7]；窗口 [5..7]：最大=A[7]=7 ✓
完整实现
📄 查看代码：完整实现
// 用单调双端队列求滑动窗口最大值 — O(N)
#include <bits/stdc++.h>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n, k;
cin >> n >> k;
vector<int> A(n);
for (int& x : A) cin >> x;
deque<int> dq; // 单调递减双端队列，存下标
vector<int> result;
for (int i = 0; i < n; i++) {
// 1. 移除超出当前窗口的元素
while (!dq.empty() && dq.front() <= i - k) {
dq.pop_front(); // ← 关键：弹出已过期的队首
}
// 2. 维护递减性质
// 从队尾移除所有小于 A[i] 的元素
// （只要 A[i] 还在窗口中，它们就不可能是最大值）
while (!dq.empty() && A[dq.back()] <= A[i]) {
dq.pop_back(); // ← 关键：从队尾弹出更小的元素
}
dq.push_back(i); // 加入当前元素
// 3. 第一个完整窗口形成后开始记录最大值
if (i >= k - 1) {
result.push_back(A[dq.front()]); // 队首 = 当前窗口最大值
}
}
for (int i = 0; i < (int)result.size(); i++) {
cout << result[i];
if (i + 1 < (int)result.size()) cout << "\n";
}
cout << "\n";
return 0;
}
复杂度：
- 每个元素最多被压入/弹出双端队列一次 → 总计 O(N)
- 空间：O(K)（双端队列）
⚠️ 常见错误 1： 忘记检查
dq.front() <= i - k来判断窗口过期。双端队列只能包含[i-k+1, i]范围内的下标。⚠️ 常见错误 2： 从队尾弹出时用
<而非<=。用<会保留相等元素，但重复值可能导致问题。用<=维护严格递减的双端队列。
3.5.5 USACO 题型：股票跨度（单调栈）
🔗 灵感： 这类题型在 USACO Bronze/Silver 中出现（「Haybale Stacking」风格）。
📄 C++ 完整代码
// 股票跨度问题：对每天 i，找在 i 之前有多少连续天价格 <= prices[i]
// （第 i 天的「跨度」）
vector<int> stockSpan(vector<int>& prices) {
int n = prices.size();
vector<int> span(n, 1);
stack<int> st; // 单调递减栈（存下标）
for (int i = 0; i < n; i++) {
while (!st.empty() && prices[st.top()] <= prices[i]) {
st.pop();
}
span[i] = st.empty() ? (i + 1) : (i - st.top());
st.push(i);
}
return span;
}
// span[i] = 到 i 为止（含）价格 <= prices[i] 的连续天数
⚠️ 第 3.5 章常见错误
-
存值而非下标 —— 始终存下标。你需要用它们检查窗口范围和记录答案。
-
双端队列中比较用
<而非<=—— 滑动窗口求最大值时，A[dq.back()] <= A[i]时弹出（严格非增）。求最小值时，A[dq.back()] >= A[i]时弹出。 -
忘记窗口过期检查 —— 滑动窗口双端队列中，记录最大值前始终检查
dq.front() < i - k + 1（或<= i - k）。 -
栈的底顶方向搞混 —— 「单调」性质指：从底到顶，栈是递增的（用于 NGE）或递减的（用于 NSE）。搞混时画图辅助。
-
NGE 和 PSE 的处理顺序：
- 下一个更大元素：从左到右遍历
- 上一个更大元素：从右到左遍历（或：从左到右遍历，在压入前记录 stack.top()）
本章总结
📌 核心要点
| 问题 | 数据结构 | 时间复杂度 | 关键操作 |
|---|---|---|---|
| 下一个更大元素（NGE） | 单调递减栈 | O(N) | 找到更大元素时弹出 |
| 上一个更小元素（PSE） | 单调递增栈 | O(N) | 压入前栈顶就是答案 |
| 直方图中最大矩形 | 单调栈（两遍） | O(N) | 左边界 + 右边界 + 宽度 |
| 滑动窗口最大值 | 单调递减双端队列 | O(N) | 维护窗口范围 + 维护递减性质 |
🧩 模板速查
📄 查看代码：🧩 模板速查
// 单调递减栈（用于 NGE / 下一个更大元素）
stack<int> st;
for (int i = 0; i < n; i++) {
while (!st.empty() && A[st.top()] < A[i]) {
answer[st.top()] = i; // i 是 st.top() 的 NGE
st.pop();
}
st.push(i);
}
// 单调递减双端队列（滑动窗口最大值）
deque<int> dq;
for (int i = 0; i < n; i++) {
while (!dq.empty() && dq.front() <= i - k) dq.pop_front(); // 移除过期元素
while (!dq.empty() && A[dq.back()] <= A[i]) dq.pop_back(); // 维护单调性
dq.push_back(i);
if (i >= k - 1) ans.push_back(A[dq.front()]);
}
❓ 常见问题
Q1：单调栈应该存值还是下标？
A：始终存下标。即使只需要值，存下标更灵活——通过
A[idx]可以取值，反之不行。特别是计算宽度时（如直方图问题），必须用下标。
Q2：如何判断用单调栈还是双指针？
A：观察问题结构——若需要「对每个元素找其左/右侧第一个更大/更小的元素」，用单调栈。若需要「维护滑动窗口的最大值」，用单调双端队列。若「两指针从两端相向移动」，用双指针。
Q3：为什么单调栈的时间复杂度是 O(N) 而不是 O(N²)？
A：均摊分析。每个元素最多被压入一次，最多被弹出一次，总共 2N 次操作，所以是 O(N)。虽然单次 while 循环可能弹出多个元素，但所有 while 循环的弹出总次数绝不超过 N。
练习题
题目 3.5.1 — 下一个更大元素 🟢 简单 对数组中每个元素，找其右侧第一个更大的元素。若不存在打印 -1。
提示
维护单调递减下标栈。处理 A[i] 时，弹出栈中所有更小的元素（它们找到了 NGE）。✅ 完整题解
#include <bits/stdc++.h>
using namespace std;
int main() {
int n; cin >> n;
vector<int> a(n); for (int& x : a) cin >> x;
vector<int> nge(n, -1);
stack<int> st;
for (int i = 0; i < n; i++) {
while (!st.empty() && a[st.top()] < a[i]) {
nge[st.top()] = a[i];
st.pop();
}
st.push(i);
}
for (int x : nge) cout << x << " "; cout << "\n";
}
样例： [2,1,5,6,2,3] → [5,5,6,-1,3,-1]
复杂度： O(N) —— 每个元素最多被压入/弹出一次。
题目 3.5.2 — 每日温度 🟢 简单 对每一天，找还需等多少天才能迎来更高温度。（LeetCode 739 风格）
提示
这正是 NGE 问题。Answer[i] = NGE下标[i] - i。用单调递减栈。✅ 完整题解
#include <bits/stdc++.h>
using namespace std;
int main() {
int n; cin >> n;
vector<int> T(n); for (int& x : T) cin >> x;
vector<int> ans(n, 0);
stack<int> st;
for (int i = 0; i < n; i++) {
while (!st.empty() && T[st.top()] < T[i]) {
ans[st.top()] = i - st.top(); // 等待天数
st.pop();
}
st.push(i);
}
for (int x : ans) cout << x << " "; cout << "\n";
}
样例： [73,74,75,71,69,72,76,73] → [1,1,4,2,1,1,0,0]
题目 3.5.3 — 滑动窗口最大值 🟡 中等 找每个大小为 K 的滑动窗口的最大值。
提示
用单调递减双端队列，维护下标范围在 [i-k+1, i] 内，队首 = 最大值。✅ 完整题解
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, k; cin >> n >> k;
vector<int> a(n); for (int& x : a) cin >> x;
deque<int> dq;
for (int i = 0; i < n; i++) {
while (!dq.empty() && dq.front() < i - k + 1) dq.pop_front();
while (!dq.empty() && a[dq.back()] <= a[i]) dq.pop_back();
dq.push_back(i);
if (i >= k - 1) cout << a[dq.front()] << " \n"[i==n-1];
}
}
样例： n=8，k=3，[1,3,-1,-3,5,3,6,7] → [3,3,5,5,6,7]
复杂度： O(N) 总计——每个元素进/出双端队列一次。
题目 3.5.4 — 直方图中最大矩形 🟡 中等 找直方图中最大矩形的面积。
提示
对每根柱子找上一个更小（左边界）和下一个更小（右边界）。宽度 = 右 - 左 - 1，面积 = 高度 × 宽度。✅ 完整题解
#include <bits/stdc++.h>
using namespace std;
int main() {
int n; cin >> n;
vector<int> H(n); for (int& x : H) cin >> x;
vector<int> left(n), right(n);
stack<int> st;
// 上一个更小（左边界）
for (int i = 0; i < n; i++) {
while (!st.empty() && H[st.top()] >= H[i]) st.pop();
left[i] = st.empty() ? -1 : st.top();
st.push(i);
}
while (!st.empty()) st.pop();
// 下一个更小（右边界）
for (int i = n-1; i >= 0; i--) {
while (!st.empty() && H[st.top()] >= H[i]) st.pop();
right[i] = st.empty() ? n : st.top();
st.push(i);
}
long long ans = 0;
for (int i = 0; i < n; i++)
ans = max(ans, (long long)H[i] * (right[i] - left[i] - 1));
cout << ans << "\n";
}
样例： [2,1,5,6,2,3] → 10（下标 2 的柱子，高度 5，宽度 2）
复杂度： O(N) —— 两次单调栈遍历。
题目 3.5.5 — 接雨水 🔴 困难 给定高度图，计算下雨后能接住多少水。
提示
对每个位置 i，接水量 = min(left_max[i], right_max[i]) - height[i]。✅ 完整题解（双指针——O(N) 时间，O(1) 空间）
#include <bits/stdc++.h>
using namespace std;
int main() {
int n; cin >> n;
vector<int> h(n); for (int& x : h) cin >> x;
int left = 0, right = n-1, maxL = 0, maxR = 0;
long long ans = 0;
while (left < right) {
if (h[left] <= h[right]) {
maxL = max(maxL, h[left]);
ans += maxL - h[left];
left++;
} else {
maxR = max(maxR, h[right]);
ans += maxR - h[right];
right--;
}
}
cout << ans << "\n";
}
样例： [0,1,0,2,1,0,1,3,2,1,2,1] → 6
复杂度： O(N) 时间，O(1) 空间。
🏆 挑战题：USACO 2016 February Silver——围牛栏 给定一个多边形，判断一个点是否在多边形内部。使用射线投射法——实现时需要仔细处理边界情况。