单调队列
模板
滑动窗口问题
给出一个长度为
- 从左到右遍历，每次把当前元素和队尾元素比较
- 当前元素更大，入队
- 当前元素更小，弹出队尾元素（有点单调栈的感觉）
- 维护一个队列 / 双端队列
- 自然出队：滑动窗口长度只有 3，弹出队首
- 比较出队：当前元素更小，弹出队尾元素
- 队列保持单调递增
- 队首元素 为滑动窗口内的最小值
例子：
python
[1, 3, -1, -3, 5, 3, 6, 7]
queue =
[1] # 1 入队
[1, 3] # 3 入队
[-1] # 3, 1 比 -1 大，从队尾弹出。-1 入队
[-3] # -1 比 -3 大，从队尾弹出。-3 入队
[-3, 5] # 5 入队
[-3, 3] # 5 比 3 大，从队尾弹出。3 入队
[3, 6] # -3 超过滑动窗口大小，从队首弹出。6 入队
[3, 6, 7] # 7 入队
# [hh, ..., tt]
ans =
[-1, -3, -3, -3, 3, 3]模拟队列写法
C++ 代码
取最小值：
- 队列单调递增（队首到队尾）
- 队首为最小值
cpp
void getMin() {
int hh = 0;
int tt = -1;
for (int i = 0; i < k - 1; i ++) {
while (hh <= tt && a[q[tt]] >= a[i]) {
tt --;
}
q[++ tt] = i;
}
for (int i = k - 1; i < n; i ++) {
while (hh <= tt && a[q[tt]] >= a[i]) {
tt --;
}
q[++ tt] = i;
while (q[hh] <= i - k) {
hh ++;
}
printf("%d ", a[q[hh]]);
}
}取最大值：
- 单调递减（队首到队尾）
- 队首为最大值
cpp
void getMax() {
int hh = 0;
int tt = -1;
for (int i = 0; i < n; i ++) {
if (hh <= tt && q[hh] < i - k + 1) {
hh ++;
}
while (hh <= tt && a[q[tt]] <= a[i]) {
tt --;
}
q[++ tt] = i;
if (i >= k - 1) {
printf("%d ", a[q[hh]]);
}
}
}- 一定要有
hh <= tt - 之所以用
if而不是while是因为每一轮最多在队首出队一次
STL 写法
- C++ 需要用到
deque - Python 的
list本身就是双端队列
python
单调队列优化 DP 问题
一般用来维护区间最值
- 前提：区间右端点变大时，左端点也在变大（同滑动窗口）
- 转移前，去掉队首无用数据
- 计算转移（直接从队首转移）
- 把
f[i]插入队尾前，去掉队尾无用数据
题目
单调队列求最值等：
- 239. 滑动窗口最大值
- LCR 184. 设计自助结算系统
- 1438. 绝对差不超过限制的最长连续子数组 1672
- 2398. 预算内的最多机器人数目 1917
- 862. 和至少为 K 的最短子数组 2307
- 1499. 满足不等式的最大值 2456
单调队列求最值等：