单调队列
1. 简介
- 单调队列与单调栈相似。建议先学习单调栈，再学习单调队列。
- 单调队列维持单调性，可以单调递增，也可以单调递减。
- 单调队列可用于优化动态规划状态转移，也可维护数据流或滑动窗口中的实时最值。
2. 实现
模板：洛谷 P1886
对于长度为 n 的序列，有一个长度为 k 的窗口。窗口从左到右每次滑动一个单位，求每次滑动后窗口内的最大值和最小值。
input
8 3
1 3 -1 -3 5 3 6 7
output
min -1 -3 -3 -3 3 3
max 3 3 5 5 6 7
思路：
- 使用双端队列
deque模拟窗口。窗口滑动时，一端加入元素、另一端移出元素；队尾既需要入队也需要出队，因此使用双端队列。 - 与单调栈相同，单调队列中存储的是元素下标。
- 先处理窗口滑动。每次求最值前，都要移除已经离开窗口的下标：从队尾加入元素，从队头移除过期元素。若 i 为当前下标，当
q.front() < i - k + 1时，说明队头下标已经离开窗口，应将其移除。 - 窗口就位后即可求最值。求最大值时，若队尾元素小于当前元素，就从队尾移除；继续比较新的队尾，直到队列为空或队尾元素不小于当前元素。求最小值同理。这样无需遍历整个窗口。
-
求最大值时，维护一个从队头到队尾单调递减的队列，队头始终对应当前窗口的最大值。
在样例中，处理元素 5 前，队列中各下标对应的值为 [3, -1, -3]（左侧为队头，右侧为队尾）。3 已离开窗口，应移除；-1 和 -3 都小于 5，且在 5 存在时不可能成为后续窗口的最大值，也应移除。
for(int i = 1; i <= n; i++) { // 求最大值
while(!q.empty() && q.front() < i - k + 1)
q.pop_front();
while(!q.empty() && a[q.back()] < a[i])
q.pop_back();
q.push_back(i);
maxi[i] = a[q.front()];
}
for(int i = 1; i <= n; i++) { // 求最小值
while(!q.empty() && q.front() < i - k + 1)
q.pop_front();
while(!q.empty() && a[q.back()] > a[i])
q.pop_back();
q.push_back(i);
mini[i] = a[q.front()];
}
3. 变形
示例 1：洛谷 P1714——求长度不超过 m 的最大子段和。
题意：给定序列 p1、…、pn，找出一个子段 [l, r]，满足 r − l + 1 ≤ m，并使 Σi = lr pi 最大。
与模板不同的是，本题要求区间和，而非直接求最值，因此需要使用前缀和。
对序列求前缀和后，得到数组 sum[]。区间 [l, r] 的和可表示为 sum[r] - sum[l-1]。
思路：
- 将 sum[i] 看作区间右端点。遍历 sum 数组时，i 已确定，右端点也随之确定，问题便转化为选择左端点。
- 区间和为 sum[r] - sum[l-1]。由于 sum[r] 固定，sum[l-1] 越小，区间和越大。
- 因此每轮循环中，用单调队列求所有合法 sum[l-1] 的最小值即可。这等价于在 sum 数组上求窗口长度为 m 的滑动窗口最小值。
示例 2：洛谷 P2216（二维）
题意：
给定一个由 a×b 个整数组成的矩阵，找出一个 n×n 的正方形区域，使其中最大值与最小值之差最小。
input
a = 5, b = 4, n = 2
1 2 5 6
0 17 16 0
16 17 2 1
2 10 2 1
1 2 2 2
output
1
思路：
- 这道题同样要求区间最值，只是从一维变成了二维；可以将二维问题拆成两个一维步骤。
- 令 c[i][j] 表示第 j 列中从 (i, j) 向上连续 n 个元素的最大值。例如 c[5][2] = 10，因为对应序列为 [2, 10]。
- max(c[i][j], c[i][j+1], …, c[i][j+n-1]) 即为以 (i, j) 为左下角的 n×n 矩形中的最大值。最小值同理，记为 d[i][j]。
- 用单调队列计算数组 c 和 d，与求一维滑动窗口最值没有区别。
- 计算完 c 和 d 后，再枚举所有矩形即可。
Tommy Chen
If you have the same hobbies, you can contact me.
