本课时有配套视频讲解，购买后即可观看（永久有效）
单调队列
一、课上练习
编程练习
二、知识总结
✨ 核心思想
单调队列（Monotonic Deque）是一种特殊的双端队列，队列中的元素始终保持单调递增或单调递减的顺序。与单调栈不同，单调队列还支持从队首弹出过期元素，因此特别适合处理滑动窗口类问题。
核心操作：
- 队尾维护单调性：入队时弹出所有破坏单调性的队尾元素
- 队首移除过期元素：当队首元素的下标超出窗口范围时弹出
每个元素最多入队一次、出队一次，总时间复杂度 O(n)。
✨ 经典问题：滑动窗口最值
问题：给定数组 a 和窗口大小 k，对于每个位置 i，求 a[i-k+1..i] 中的最大值和最小值。
滑动窗口最大值和最小值
1#include <bits/stdc++.h>
2using namespace std;
3
4int main() {
5 int n, k;
6 scanf("%d%d", &n, &k);
7 vector<int> a(n);
8 for (int i = 0; i < n; i++) scanf("%d", &a[i]);
9
10 // 求滑动窗口最小值（维护单调递增队列）
11 {
12 deque<int> dq; // 存下标
13 for (int i = 0; i < n; i++) {
14 // 移除超出窗口的元素
15 while (!dq.empty() && dq.front() <= i - k)
16 dq.pop_front();
17 // 维护单调递增：移除所有 >= a[i] 的队尾元素
18 while (!dq.empty() && a[dq.back()] >= a[i])
19 dq.pop_back();
20 dq.push_back(i);
21
22 if (i >= k - 1)
23 printf("%d ", a[dq.front()]); // 队首就是窗口最小值
24 }
25 printf("\n");
26 }
27
28 // 求滑动窗口最大值（维护单调递减队列）
29 {
30 deque<int> dq;
31 for (int i = 0; i < n; i++) {
32 while (!dq.empty() && dq.front() <= i - k)
33 dq.pop_front();
34 while (!dq.empty() && a[dq.back()] <= a[i])
35 dq.pop_back();
36 dq.push_back(i);
37
38 if (i >= k - 1)
39 printf("%d ", a[dq.front()]);
40 }
41 printf("\n");
42 }
43
44 return 0;
45}✨ 执行示例
以数组 [1, 3, -1, -3, 5, 3, 6, 7]，k=3 为例，求窗口最大值：
维护单调递减队列（队首最大）：
| i | a[i] | 操作 | deque（下标→值） | 窗口最大值 |
|---|---|---|---|---|
| 0 | 1 | 入队 | [0→1] | - |
| 1 | 3 | 弹出 1（3>1），入队 | [1→3] | - |
| 2 | -1 | 入队 | [1→3, 2→-1] | 3 |
| 3 | -3 | 入队 | [1→3, 2→-1, 3→-3] | 3 |
| 4 | 5 | 弹出队首 1（过期）；弹出 -3, -1, 3（5>它们）；入队 | [4→5] | 5 |
| 5 | 3 | 入队 | [4→5, 5→3] | 5 |
| 6 | 6 | 弹出 3（6>3），入队 | [6→6] | 6 |
| 7 | 7 | 弹出 6（7>6），入队 | [7→7] | 7 |
输出：3 3 5 5 6 7
关键理解：队列中保存的不是窗口内所有元素，而是"有可能成为未来窗口最大值的候选者"。一个元素如果比后面入队的元素小，它永远不可能成为最大值，所以被淘汰。
✨ 单调队列优化 DP
单调队列最重要的高级应用是优化动态规划。当 DP 转移方程形如：
dp[i] = min/max(dp[j] + cost(j)) for j in [i-k, i-1]
即从一个固定长度的窗口中选择最优的转移来源时，可以用单调队列将每次转移从 O(k) 优化到 O(1)。
例题：跳跃游戏
问题：有 n 个格子，每个格子有权值 a[i]。从格子 i 可以跳到 i+1, i+2, ..., i+k 中的任意一个。从格子 1 出发到格子 n，求经过的格子权值之和的最大值。
跳跃游戏 - 单调队列优化 DP
1#include <bits/stdc++.h>
2using namespace std;
3
4int main() {
5 int n, k;
6 scanf("%d%d", &n, &k);
7 vector<int> a(n + 1);
8 vector<long long> dp(n + 1, LLONG_MIN);
9
10 for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
11
12 dp[1] = a[1];
13 deque<int> dq; // 存下标，维护 dp 值的单调递减队列
14 dq.push_back(1);
15
16 for (int i = 2; i <= n; i++) {
17 // 移除超出窗口的元素
18 while (!dq.empty() && dq.front() < i - k)
19 dq.pop_front();
20
21 // 转移：dp[i] = dp[dq.front()] + a[i]
22 if (!dq.empty())
23 dp[i] = dp[dq.front()] + a[i];
24
25 // 维护单调递减：新入队的 dp[i] 比队尾大就弹出队尾
26 while (!dq.empty() && dp[dq.back()] <= dp[i])
27 dq.pop_back();
28 dq.push_back(i);
29 }
30
31 printf("%lld\n", dp[n]);
32 return 0;
33}例题：多重背包的单调队列优化
多重背包问题中，每种物品可以选 0 到 s[i] 个。朴素 DP 是 O(N V S)，用单调队列可以优化到 O(N * V)。
多重背包 - 单调队列优化（核心思路）
1#include <bits/stdc++.h>
2using namespace std;
3
4int main() {
5 int N, V;
6 scanf("%d%d", &N, &V);
7
8 vector<int> dp(V + 1, 0);
9
10 for (int i = 0; i < N; i++) {
11 int v, w, s; // 体积、价值、数量
12 scanf("%d%d%d", &v, &w, &s);
13
14 // 按余数分组：j % v 相同的位置之间互相转移
15 vector<int> old_dp = dp; // 备份
16
17 for (int r = 0; r < v; r++) {
18 deque<int> dq; // 存下标 (j/v 的值)
19
20 for (int j = r, cnt = 0; j <= V; j += v, cnt++) {
21 // 当前值：old_dp[j] - cnt * w
22 int val = old_dp[j] - cnt * w;
23
24 // 移除超出窗口的（窗口大小为 s+1）
25 while (!dq.empty() && dq.front() < cnt - s)
26 dq.pop_front();
27
28 // 维护单调递减
29 while (!dq.empty() &&
30 old_dp[r + dq.back() * v] - dq.back() * w <= val)
31 dq.pop_back();
32 dq.push_back(cnt);
33
34 // 转移
35 dp[j] = old_dp[r + dq.front() * v] - dq.front() * w + cnt * w;
36 }
37 }
38 }
39
40 printf("%d\n", dp[V]);
41 return 0;
42}✨ 解题步骤详解
遇到以下情况时考虑单调队列：
- 滑动窗口最值：最直接的应用
- DP 转移中有固定窗口约束：
dp[i] = min/max(dp[j] + ...) for j in [L(i), R(i)]，且窗口端点单调递增 - 多重背包优化：经典的单调队列 DP 优化
使用单调队列的条件：
- 窗口的左右端点随 i 单调递增（不能回退）
- 求的是窗口内的最值
不适用的情况：
- 窗口端点不单调
- 需要窗口内第 k 大（需要平衡树等更复杂的结构）
✨ 单调栈 vs 单调队列
| 特性 | 单调栈 | 单调队列 |
|---|---|---|
| 数据结构 | 栈（一端操作） | 双端队列（两端操作） |
| 队首弹出 | 不支持 | 支持（移除过期元素） |
| 典型问题 | NGE、柱状图矩形 | 滑动窗口最值、DP 优化 |
| 窗口约束 | 无 | 有（固定或单调窗口） |
✨ 常见错误
- 窗口边界判断错误：
dq.front() <= i - k还是< i - k，取决于窗口定义是否包含端点 - 单调性方向搞反：求最大值用递减队列，求最小值用递增队列
- DP 优化中新旧 dp 值混用：多重背包中必须用上一轮的 dp 值，需要备份
- 忘记在转移前检查队列非空：队列可能为空（窗口内没有合法状态）
- 数组越界：队列中存的下标可能越界，特别是在 DP 优化中
✨ 算法评价
| 应用 | 暴力复杂度 | 单调队列优化后 |
|---|---|---|
| 滑动窗口最值 | O(nk) | O(n) |
| 跳跃游戏 DP | O(nk) | O(n) |
| 多重背包 | O(NVS) | O(NV) |
单调队列是竞赛中非常重要的优化技巧。它的本质是：在单调移动的窗口中，维护一组"有潜力成为最优解的候选者"，淘汰那些永远不可能胜出的元素。理解这个本质后，遇到新问题时就能灵活运用。
三、课后练习
编程练习
- 质量检测：L49918