单调队列
引入
如果一个选手比你小还比你强，你就可以退役了。
单调队列是一种主要用于解决滑动窗口类问题的数据结构，即，在长度为 \(n\) 的序列中，求每个长度为 \(m\) 的区间的区间最值。它的时间复杂度是 \(O(n)\)，在这个问题中比 \(O(n\log n)\) 的 ST 表和线段树更优。
定义
顾名思义，单调队列的重点分为「单调」和「队列」。
「单调」指的是元素的「规律」——递增（或递减）。
「队列」指的是元素只能从队头和队尾进行操作。
例题
题目描述
有一个长为 \(n\) 的序列 \(a\)，以及一个大小为 \(k\) 的窗口。现在这个从左边开始向右滑动，每次滑动一个单位，求出每次滑动后窗口中的最大值和最小值。
例如：
The array is \([1,3,-1,-3,5,3,6,7]\), and \(k = 3\)。
输入格式
输入一共有两行，第一行有两个正整数 \(n,k\)。
第二行 \(n\) 个整数，表示序列 \(a\)。输出格式
输出共两行，第一行为每次窗口滑动的最小值。
第二行为每次窗口滑动的最大值。
解释
要求的是每连续的 \(k\) 个数中的最大（最小）值，很明显，当一个数进入所要 "寻找" 最大值的范围中时，若这个数比其前面（先进队）的数要大，显然，前面的数会比这个数先出队且不再可能是最大值。
也就是说——当满足以上条件时，可将前面的数 "弹出"，再将该数真正 push 进队尾。
这就相当于维护了一个递减的队列，符合单调队列的定义，减少了重复的比较次数，不仅如此，由于维护出的队伍是查询范围内的且是递减的，队头必定是该查询区域内的最大值，因此输出时只需输出队头即可。
显而易见的是，在这样的算法中，每个数只要进队与出队各一次，因此时间复杂度被降到了 \(O(n)\)。
而由于查询区间长度是固定的，超出查询空间的值再大也不能输出，因此还需要 site 数组记录第 \(i\) 个队中的数在原数组中的位置，以弹出越界的队头。
过程
例如我们构造一个单调递增的队列会如下：
原序列为：
1 3 -1 -3 5 3 6 7
因为我们始终要维护队列保证其 递增 的特点，所以会有如下的事情发生：
| 操作 | 队列状态 |
|---|---|
| 1 入队 | {1} |
| 3 比 1 大，3 入队 | {1 3} |
| -1 比队列中所有元素小，所以清空队列 -1 入队 | {-1} |
| -3 比队列中所有元素小，所以清空队列 -3 入队 | {-3} |
| 5 比 -3 大，直接入队 | {-3 5} |
| 3 比 5 小，5 出队，3 入队 | {-3 3} |
| -3 已经在窗体外，所以 -3 出队；6 比 3 大，6 入队 | {3 6} |
| 7 比 6 大，7 入队 | {3 6 7} |
实现
#include <iostream>
#define MAXN 1000005
using namespace std;
int n, k, h, t;
int a[MAXN], q[MAXN];
int read(){
int t = 1, x = 0;char ch = getchar();
while(!isdigit(ch)){if(ch == '-')t = -1;ch = getchar();}
while(isdigit(ch)){x = (x << 1) + (x << 3) + (ch ^ 48);ch = getchar();}
return x * t;
}
void write(int x){
if(x < 0){putchar('-');x = -x;}
if(x >= 10)write(x / 10);
putchar(x % 10 + '0');
}
int main(){
n = read();k = read();
for(int i = 1 ; i <= n ; i ++)a[i] = read();
h = 1;t = 0;
for(int i = 1 ; i <= n ; i ++){
while(h <= t && q[h] + k <= i)h ++;
while(h <= t && a[q[t]] > a[i])t --;
q[++ t] = i;
if(i >= k){
write(a[q[h]]);putchar(' ');
}
}
putchar('\n');h = 1;t = 0;
for(int i = 1 ; i <= n ; i ++){
while(h <= t && q[h] + k <= i)h ++;
while(h <= t && a[q[t]] < a[i])t --;
q[++ t] = i;
if(i >= k){
write(a[q[h]]);putchar(' ');
}
}
putchar('\n');return 0;
}