顾名思义，单调队列的重点分为 “单调” 和 “队列”
“单调” 指的是元素的的 “规律”——递增（或递减）
“队列” 指的是元素只能从队头和队尾进行操作
- 单调递增队列：保证队列头元素一定是当前队列的最小值，用于维护区间的最小值。
- 单调递减队列：保证队列头元素一定是当前队列的最大值，用于维护区间的最大值。
1、对于单调递增队列，对于一个元素如果它大于等于队尾元素， 那么直接把元素进队， 如果这个元素小于队尾元素，则将队尾元素出队列，直到满足这个元素大于等于队尾元素。
2、对于单调递减队列，对于一个元素如果它小于等于队尾元素， 那么直接把元素进队， 如果这个元素大于队尾元素，则将队尾元素出队列，直到满足这个元素小于等于队尾元素。
3、判断队头元素是否在待求解的区间之内，如果不在，就将其删除。（这个很好理解呀，因为单调队列的队头元素就是待求解区间的极值）
4、经过上面两个操作，取出 队列的头元素 ，就是 当前区间的极值 。
可以发现队列中的元素都是单调递减的（不然也就不叫单调递减队列啦），同时既有入队列的操作、也有出队列的操作。
实现单调队列，主要分为三个部分：
- 去尾操作 ：队尾元素出队列。当队列有新元素待入队，需要从队尾开始，删除影响队列单调性的元素，维护队列的单调性。(删除一个队尾元素后，就重新判断新的队尾元素)
去尾操作结束后，将该新元素入队列。
- 删头操作 ：队头元素出队列。判断队头元素是否在待求解的区间之内，如果不在，就将其删除。（这个很好理解呀，因为单调队列的队头元素就是待求解区间的极值）
- 取解操作 ：经过上面两个操作，取出 队列的头元素 ，就是 当前区间的极值 。
参考代码
#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;
}