简介
单调队列，顾名思义，就是内部元素保持单调性的数据结构，同时又有着类似队列的尾进头出。
基本思想
保持队列最基本的操作（FIFO），但为了维护单调性，在入队的时候需要从尾部开始判断大小关系，将不符合的元素从尾部弹出队列，并将最新元素补充在尾部。
取最值即取头部值，在此之前需要判断该值是否在有效范围内，若否，不断从头部弹出直至有效最值出现（注意：此处并不会出现队列弹空的情况）。
例题
滑动窗口
题意
给定n个元素，窗口宽度是m，随着窗口的滑动，依次输出窗中元素的最大值和最小值。
思路
最大值和最小值思路相同，此处只讨论最大值。
首相考虑一个较大值的控制范围，即以它为最大值的区间，为窗口长度。换言之，一个值的有效范围就是窗口长度。
那么我们就只需要不断更新维护单调队列，并且每次取有效最大值即可。
Code
//////////////////////////////////////////////////////////////////////
//Target: 洛谷 P1886 滑动窗口
//@Author: Pisceskkk
//Date: 2019-2-21
//////////////////////////////////////////////////////////////////////
#include<cstdio>
#define N 1000002
using namespace std;
int n,l;
int h=0,t=1,ma[N],mi[N];
int main(){
scanf("%d%d",&n,&l);
for(int i=1;i<=n;i++){
int a;
scanf("%d",&a);
ma[++h]=a;mi[h]=a;
for(int j=h-1;j>=t;j--){
if(ma[j]>=a)break;
else ma[j]=a;
}
for(int j=h-1;j>=t;j--){
if(mi[j]<=a)break;
else mi[j]=a;
}
if(i>=l)t++;
}
for(int i=1;i<=n-l+1;i++)printf("%d ",mi[i]);
printf("
");
for(int i=1;i<=n-l+1;i++)printf("%d ",ma[i]);
return 0;
}