单调队列
单调队列的重点是维护队列内元素的单调性。准确地说不是「队列」而是「双向队列」，因为需要在队头和队尾增删元素。
假定要维护队列的元素是递增的，则当一个元素入队时，从后往前检查元素：
- 如果此元素比要插入的元素大，则删去
- 直到队被清空或者当前元素小于等于要插入的元素，我们再将要插入元素入队
适用情况：如果在连续的一个区间内要求一些子区间的某种最值，而且满足只要两个元素i和j满足一个大小关系，之后区间的最值必然不涉及其中一个元素。比如，在下面的例题中，如果元素i在j之前，且i的值小于j，那么后面区间的最大值就必然不是i，所以递增的元素对是冗余的，应该维护一个递减的序列。
例题
给出一个长度为n的数组，编程输出每k个连续的数中的最大值和最小值
如果维护一个单调队列，每个元素最多入队出队一次，线性时间复杂度。求最大值维护递减序列，最小值维护递增序列；每次查询就返回队首。因为这里窗口固定是k，需要再额外判断一下队首是否在窗口内。
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#define maxn 1000100
using namespace std;
int q[maxn], a[maxn];
int n, k;
void getmin() {
int head = 0, tail = 0;
for (int i = 1; i < k; i++) {
while (head <= tail && a[q[tail]] >= a[i]) tail--;
q[++tail] = i;
}
for (int i = k; i <= n; i++) {
while (head <= tail && a[q[tail]] >= a[i]) tail--;
q[++tail] = i;
while (q[head] <= i - k) head++;
printf("%d ", a[q[head]]);
}
}
void getmax() {
int head = 0, tail = 0;
for (int i = 1; i < k; i++) {
while (head <= tail && a[q[tail]] <= a[i]) tail--;
q[++tail] = i;
}
for (int i = k; i <= n; i++) {
while (head <= tail && a[q[tail]] <= a[i]) tail--;
q[++tail] = i;
while (q[head] <= i - k) head++;
printf("%d ", a[q[head]]);
}
}
int main() {
scanf("%d%d", &n, &k);
for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
getmin();
printf("\n");
getmax();
printf("\n");
return 0;
}