单调队列
典型运用：求滑动窗口中的 最大值 or 最小值
举个例子：
给定输入序列：1、3、-1、-3、5、3、6、7，目的是将所有长度为3的滑动窗口中的max和min输出
则有：
和单调栈的思考模式差不多，先想想暴力求解是如何做的。
首先对于窗口我们用队列来维护，先从队列为空开始维护，
开始枚举每个元素，元素从队尾插入，此后队列中时刻都是维护的当前窗口中所有元素（k个元素，上图k=3），每一次移动的时候，分2步来操作：
- ① 将新元素插到队尾
- ② 把滑出去的元素从队头弹出
每一次求取极值的时候，暴力做法就是遍历队列中所有元素O(k)（窗口中含k个元素），
对于这种暴力做法的时间复杂度为O(nk)，n和k都是<=1e6，肯定会超时的
优化思路：
方式和单调栈类似，分析队列中是不是有些元素是“没用”的，把这些“没用”的元素删掉，观察是否会得到单调性，我们将目光锁定在一个窗口中：3、-1、-3，
注意，现在我们在模拟求一个窗口内的min的过程，
首先，当-3加入队列后，因为-3是小于这个窗口第一个元素3的，且第一个元素3在-3的左侧，所以第一个元素3会先弹出队列，
换句通俗点的话说：只要“-3在的一天，因为第一个元素3一定是比它大的，所以第一个元素3一定不会被当成min输出，永无出头之日，且-3会在第一个元素3之后弹出队列”
上述可以断定，第一个元素 3 一定不会被当做min输出，我们将其删掉，第二个元素-1也是一样，它位于-3的左侧，所以-1会在-3后方被弹出队列，由于-3 <= -1，所以-1也是不会被当做min输出的，将它删掉。
总结一下，只要队列中存在这样的情况（前面的元素比后面的元素大）：a[x] >= a[y] (x <= y)，那么我们就可以断定前面的元素一定“没用”（后面的元素 会在 前面的元素 之后 弹出，且后面元素还小于等于前面元素）。
因此，只要有上述这样“逆序对”的情况发生的话，我们就可以将较大的元素删掉，当将所有这样的逆序对删掉的话，整个队列就会成为一个严格单调上升的了。
我们的目标是求这个严格单调上升队列中的min，显然找到最左侧的队头元素q[hh]即可（O(1)）
（这个队列一旦有了单调性就很方便了，如果寻找极值取队列头尾即可，如果查找某个值用二分即可，各种优化都可）
求窗口内的max与上面同理，这里不作过多赘述了。
细节：
怎么知道队首元素何时弹出呢？
对本题而言，i （当前枚举的右端点） 和 k （窗口的长度）都是知道的，注意队列q中存的不是确切的元素值，而是存的元素下标，因此，我们就可以判断：队头的下标是否超出了 [i-k+1, i] 这个长度为k的范围（q[hh]<i-k+1），如果超出，则把队头删掉（代码中有体现）
时间复杂度：
O ( n ) O(n) O(n)
求min代码片段：
hh=0, tt=-1;
for(int i=0; i<n; ++i)
{
//判队头是否已经弹出窗口，每次只会弹出1个数，因此用if不用while
if(hh<=tt && q[hh]<i-k+1) hh++; //如果两个条件(前者表示队列不空，后者具体见上)均满足，说明q[hh]已经出了队列，则hh++
while(hh<=tt && a[q[tt]]>=a[i]) tt--; //若队尾的元素大于等于新插入的元素，那么队尾就“没用“了，出队（注意q[tt]是下标，取元素值即为a[q[tt]]）
//注意本题是从前k个数开始输出的，当元素不足k个就不用输出了，因此这里得特判一下
q[++tt] = i; //要先将当前元素插入队尾后才输出，因为i可为min
if(i>=k-1) printf("%d ", a[q[hh]]); //满足这条才输出
}
求max代码片段（与求min对称）：
hh=0, tt=-1;
for(int i=0; i<n; ++i)
{
if(hh<=tt && q[hh]<i-k+1) hh++;
while(hh<=tt && a[q[tt]]<=a[i]) tt--; //与求min对称
q[++tt] = i;
if(i>=k-1) printf("%d ", a[q[hh]]);
}
代码：
手写双端队列写法
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6+10;
int n, k, q[N], a[N];
int hh, tt;
int main()
{
scanf("%d%d", &n, &k);
for(int i=0; i<n; i++) scanf("%d", &a[i]);
hh=0, tt=-1;
for(int i=0; i<n; ++i)
{
if(hh<=tt && q[hh]<i-k+1) hh++;
while(hh<=tt && a[q[tt]]>=a[i]) tt--;
q[++tt] = i;
if(i>=k-1) printf("%d ", a[q[hh]]);
}
puts("");
hh=0, tt=-1;
for(int i=0; i<n; ++i)
{
if(hh<=tt && q[hh]<i-k+1) hh++;
while(hh<=tt && a[q[tt]]<=a[i]) tt--;
q[++tt] = i;
if(i>=k-1) printf("%d ", a[q[hh]]);
}
puts("");
return 0;
}
STL双端队列deque写法
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6+10;
int n, k;
int a[N];
deque<int> que;
int main()
{
cin>>n>>k;
for(int i=0; i<n; ++i) scanf("%d", &a[i]);
for(int i=0; i<n; ++i)
{
if(!que.empty() && que.front()<i-k+1) que.pop_front();
while(!que.empty() && a[que.back()]>=a[i]) que.pop_back();
que.push_back(i);
if(i>=k-1) printf("%d ", a[que.front()]);
}
puts("");
que.clear();
for(int i=0; i<n; ++i)
{
if(!que.empty() && que.front()<i-k+1) que.pop_front();
while(!que.empty() && a[que.back()]<=a[i]) que.pop_back();
que.push_back(i);
if(i>=k-1) printf("%d ", a[que.front()]);
}
puts("");
return 0;
}