单调队列使用范围：
滑动区间的极值查询与维护
单调队列的原理：
单调队列需要持续维护队列的单调性，我们假设该队列为单增队列，那么最小值可以在队尾取得。
如图是一个刚建立的队列
接下来思考插入一个元素怎么处理：我们从队首开始看，如果队首的元素比目前需要插入的值大，那么原先队列的那个值在滑动过程中就不会成为最小值（因为后来的比目前的小）。所以，如果队首的元素一直大于目前的元素，就可以不断踢掉队首，直到目前的值比队首的值大。（之所以在这里放元素，是因为如果区间滑动的过程中这个值一直是最大的话，前面的值都会被删除）那么这个单增队列就完成维护了。
接下来，就要思考如何处理区间滑动问题。假设这里的滑动为定长（后续可以通过不间断的修改k达成不定长度维护），那么，我只要从队尾开始，一直把不在区间范围内的数据踢掉就行，最后留下来的就是在该区间范围内的最大值。
最后一步，便是查询区间最值，直接输出队尾元素即可。
单调队列操作：
class Ordered_Queue
{
private:
int head;//队首
int tail;//队尾
int cnt;//目前的位置
int val[MaxN];//储存的值
int pos[MaxN];//储存的位置
int k;//区间长度
public:
void init(int dis);//初始化
void add(int x);//移动滑块（最新的值为x）
int max_v();//查询最大值
}
初始化
void Ordered_Queue::init(int dis)
{
head = 0;
tail = 1;
cnt = 0;
k = dis;
}
移动滑块（加上删除前置元素）
void Ordered_Queue::add(int x)
{
cnt++;
while(tail <= head && pos[tail] <= cnt - k)
tail++;
while(tail <= head && val[head] <= x)//这里的大于小于号代表着维护的最值类型，大于号为最小值，小于号为最大值。
head--;
head++;
val[head] = x;
pos[head] = cnt;
}
查询最大值
int max_v()
{
return val[tail];
}
连贯代码（洛谷P1886模板）
传送连接：点我传送
#include <iostream>
using namespace std;
int val[1000010], pos[1000010], head, tail;
int a[1000010], n;
int main() {
int n, k;
cin >> n >> k;
for (int i = 1 ; i <= n; i++)
cin >> a[i];
int head = 0;
int tail = 1;
for (int i = 1 ; i <= n; i++) {
while (tail <= head && pos[tail] <= i - k)
tail++;
while (tail <= head && val[head] >= a[i])
head--;
head++;
val[head] = a[i];
pos[head] = i;
if (i >= k)
cout << val[tail] << " ";
}
cout << endl;
head = 0;
tail = 1;
for (int i = 1; i <= n ; i++) {
while (tail <= head && pos[tail] <= i - k)
tail++;
while (tail <= head && val[head] <= a[i])
head--;
head++;
val[head] = a[i];
pos[head] = i;
if (i >= k)
cout << val[tail] << " ";
}
return 0;
}