一、简述
本节介绍一下单调队列及其一些应用。
二、单调队列
单调队列就是队列元素满足单调性的一类数据结构，主要用于解决滑动窗口类的问题，即维护一个区间的最值，在应用时时间复杂度是 \(O(n)\) 的。
一般的，如果我们维护区间的最小值，那么维护的队列是单调递增的；如果是维护区间的最大值，那么队列是单调递减的。
三、例题
1.[AcWing154.滑动窗口]
题目描述
给定一个大小为 \(n≤10^6\) 的数组。
有一个大小为 \(k\) 的滑动窗口，它从数组的最左边移动到最右边。
你只能在窗口中看到 \(k\) 个数字。
每次滑动窗口向右移动一个位置。
以下是一个例子：
该数组为 [1 3 -1 -3 5 3 6 7]，\(k\) 为 \(3\)。
| 窗口位置 | 最大值 | 最小值 |
|---|---|---|
| [1 3 -1] -3 5 3 6 7 | 3 | -1 |
| 1 [3 -1 -3] 5 3 6 7 | 3 | -3 |
| 1 3 [-1 -3 5] 3 6 7 | 5 | -3 |
| 1 3 -1 [-3 5 3] 6 7 | 5 | -3 |
| 1 3 -1 -3 [5 3 6] 7 | 6 | 3 |
| 1 3 -1 -3 5 [3 6 7] | 7 | 3 |
你的任务是确定滑动窗口位于每个位置时，窗口中的最大值和最小值。
输入格式
输入包含两行。
第一行包含两个整数 \(n\) 和 \(k\)，分别代表数组长度和滑动窗口的长度。
第二行有 \(n\) 个整数，代表数组的具体数值。
同行数据之间用空格隔开。
输出格式
输出包含两个。
第一行输出，从左至右，每个位置滑动窗口中的最小值。
第二行输出，从左至右，每个位置滑动窗口中的最大值。
输入样例
8 3
1 3 -1 -3 5 3 6 7
输出样例
-1 -3 -3 -3 3 3
3 3 5 5 6 7
解题思路
这是单调队列的模板题。
以求最小值为例。我们用队列维护一个单调递增的队列。从前往后遍历序列，首先队列非空并且队尾元素大于等于当前元素，那么一直弹出队尾，为什么？因为我们要维护最小值，队列中的元素都在区间内，那么当前元素更小，那么队列中比它大的元素一定不会是二者所在区间的最小值，所以要弹出。然后将当前元素入队。如果说队头元素不在区间内了，那么队头要弹出。最后队头就是就是区间最小值。
最大值类似。
C++代码
#include<iostream>
using namespace std;
const int N = 1e6 + 10;
int n, k;
int q[N], a[N];
int main()
{
scanf("%d%d", &n, &k);
for (int i = 1; i <= n; i ++)
scanf("%d", &a[i]);
int hh = 0, tt = -1;
for (int i = 1; i <= n; i ++)
{
while (hh <= tt && a[q[tt]] >= a[i])
tt --;
q[++ tt] = i;
if (q[hh] + k - 1 < i)
hh ++;
if (i >= k) printf("%d ", a[q[hh]]);
}
printf("\n");
hh = 0, tt = -1;
for (int i = 1; i <= n; i ++)
{
while (hh <= tt && a[q[tt]] <= a[i])
tt --;
q[++ tt] = i;
if (q[hh] + k - 1 < i)
hh ++;
if (i >= k) printf("%d ", a[q[hh]]);
}
return 0;
}
2.[Daimayuan Online Judge.最大连续区间和]
题目描述
给你 \(n\) 个数字 \(a_1,a_2,...,a_n\) 和两个整数 \(l,r\)，你需要在 \(a_1,a_2,...,a_n\) 中选出一段连续的区间满足区间长度 \(∈[l,r]\) 并且区间内的数字的和最大。
请求出满足条件的最大连续区间和。
输入格式
第一行三个整数 \(n,l,r\)。
接下来一行 \(n\) 个整数 \(a_1,a_2,...,a_n\)。
输出格式
输出一行一个数，表示答案。
数据范围
对于 \(100\%\) 的数据，保证 \(1≤l≤r≤n≤10^5,−1000≤a_i≤1000\)。
输入样例
6 2 3
-1 3 -3 4 -5 4
输出样例
4
解题思路
首先看到区间和，那么就要想到前缀和。我们固定 \(s[i]\)，也就是 \(\sum\limits_{k=1}^i a[k]\)，然后区间长度为 \([l,r]\)，那么也就是考虑 \(s[i+l-1]\) 至 \(s[i+r-1]\)，那么 \(s[x]\) 也就在这之间，有 \(x\in[i+l-1,i+r-1]\)。我们要在这个区间内找到 \(s[x]\) 的最大值。
C++代码
#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
int n, l, r;
int a[N], s[N];
int q[N], hh = 0, tt = -1;
int main()
{
scanf("%d%d%d", &n, &l, &r);
for (int i = 1; i <= n; i ++)
{
scanf("%d", &a[i]);
s[i] = s[i - 1] + a[i];
}
int x = l, res = - (1 << 30);
for (int i = 1; i + l - 1 <= n; i ++)
{
while (x <= i + r - 1 && x <= n)
{
while (hh <= tt && s[q[tt]] <= s[x])
tt --;
q[++ tt] = x;
x ++;
}
if (q[hh] < i + l - 1)
hh ++;
res = max(res, s[q[hh]] - s[i - 1]);
}
printf("%d\n", res);
return 0;
}
3.[Daimayuan Online Judge.覆盖]
题目描述
在一张网格图中，每一列有且仅有一个格子被小蜗涂了色，第 \(i\) 列被涂色的格子的高度为 \(a_i\)。
现在有一块高度为 \(h\) 的长方形幕布（挂在高度 \(x\) 的时候能盖住的高度区间为 \([x−h+1,x]\)），幕布可以在列方向无限延伸（也就是说幕布的宽度可以是任意值）。请问在固定幕布挂的高度后，这块幕布最多可以覆盖住连续多少列的被涂色的格子？
输入格式
第一行两个整数 \(n,h\)。
接下来一行 \(n\) 个整数 \(a_1,a_2,...,a_n\)。
输出格式
输出一行一个数，表示答案。
数据范围
对于 \(100\%\) 的数据，保证 \(1≤n≤10^5,1≤h,a_i≤10^6\)。
输入样例
7 4
1 4 5 3 6 1 4
输出样例
4
解题思路
我们维护一个区间，区间为 \([i,j]\)，并且这个区间的最大值和最小值之差小于 \(h\)，固定左端点，然后尽可能延伸右端点。区间的最值我们用单调队列来维护。然后左端点变为 \(i+1\)，\([i+1,j]\) 肯定是符合条件的，我们继续延伸 \(j\) 即可。注意，要先判断队头是否出队。
C++代码
#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
int n, h;
int a[N];
int q_max[N], q_min[N];
int hh_max, tt_max = -1;
int hh_min, tt_min = -1;
int main()
{
scanf("%d%d", &n, &h);
for (int i = 1; i <= n; i ++)
scanf("%d", &a[i]);
int j = 0, ans = 0;
for (int i = 1; i <= n; i ++)
{
if (hh_max <= tt_max && q_max[hh_max] < i)
hh_max ++;
if (hh_min <= tt_min && q_min[hh_min] < i)
hh_min ++;
while (j <= n && (j <= i || a[q_max[hh_max]] - a[q_min[hh_min]] <= h))
{
j ++;
if (j > n)
break;
while (hh_max <= tt_max && a[q_max[tt_max]] <= a[j])
tt_max --;
q_max[++ tt_max] = j;
while (hh_min <= tt_min && a[q_min[tt_min]] >= a[j])
tt_min --;
q_min[++ tt_min] = j;
}
ans = max(ans, j - i);
}
printf("%d\n", ans);
return 0;
}