单调队列的定义
顾名思义，单调队列就是队内元素具有单调性的队列。根据需要我们可以直接从队头取出队列中的最大值或最小值，并且剩下的元素仍然具有单调性。
通过一个经典题目来了解单调队列
滑动窗口-AcWing题库
给定一个大小为 n≤106的数组。
有一个大小为 k的滑动窗口，它从数组的最左边移动到最右边。
你只能在窗口中看到 k个数字。
每次滑动窗口向右移动一个位置。
你的任务是确定滑动窗口位于每个位置时，窗口中的最大值和最小值。
首先我们来思考一下暴力的做法，从第一个数开始到第 n-k 个数每次遍历k个数，那么时间复杂度大概就是O(nk)，这样当k稍大点时，就会TEL啦。
这时我们就可以用到单调队列了。毕竟满足单调性的话我们只要取队列的队头就可以了，减少了很多不必要的比较。因为窗口中只能看到k个数字，所以
我们要维护一个大小为 k 的单调队列。具体怎么做看代码
点击查看代码
#include<bits/stdc++.h>
using namespace std;
int q1[1000010],q2[1000010],max_value[1000010],min_value[1000010],value[1000010];
int main() {
int n, k,cnt=0;
cin >> n >> k;
int head01 = 0, tail01 = -1,head02=0,tail02=-1;
for (int i = 0; i < n; i++) {
cin >> value[i];
}
for (int i = 0; i < n; i++) {
//在队列不为空的情况下，如果队列中的元素多于k个，队头就出队
while (tail01>=head01&&i-q1[head01] >=k ) head01++;
//在队列不为空的情况下，如果队尾元素下标对应的值小于要入队的值，
//说明该元素‘没有成为最大元素的潜力’，队尾元素出队
while (tail01 >= head01 && value[q1[tail01]] < value[i]) tail01--;
q1[++tail01] = i;
//在队列不为空的情况下，如果队列中的元素多于k个，队头就出队
while (tail02>=head02&&i-q2[head02] >= k) head02++;
//在队列不为空的情况下，如果队尾元素下标对应的值大于要入队的值，
//说明该元素‘没有成为最小元素的潜力’，队尾元素出队
while (tail02 >= head02 && value[q2[tail02]] > value[i]) tail02--;
//新元素入队
q2[++tail02] = i;
//当队内元素达到k个时再记录答案
if (i >= k - 1) {
max_value[cnt] = value[q1[head01]];
min_value[cnt] = value[q2[head02]];
++cnt;
}
}
for (int i = 0; i < cnt; i++) cout << min_value[i]<<" ";
cout << "\n";
for (int i = 0; i < cnt; i++) cout << max_value[i] << " ";
}