什么是单调队列：头元素一直是队列当中的最大值，队列中的值按照递减顺序排列，可以从末尾插入一个元素，或从两段删除元素
1.插入元素，为了保证队列的单调性（这里假设为递减性），在插入元素v时要将对位的元素和v比较，如果队尾的元素不大于v，删掉，直到队尾元素大于v，再将v插入队尾
2.删除元素，队尾的删除如上所述，队首的删除是一直到队首的元素不存在集合时，再将其删除
模板题poj2823
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#define maxn 1000005 using namespace std; int l,r,n,k,a[maxn],q[maxn];//队列里保存元素的下标 void workmin(){
int l=,r=,i=;
for(;i<k-;i++){//将前k个插入队尾
while(l<=r && a[q[r]]>a[i])r--;
q[++r]=i;
}
for(;i<n;i++){
if(q[l]<=i-k)l++;//删掉首元素
while(l<=r&&a[q[r]]>a[i]) r--;
q[++r]=i;//新元素入队尾
printf("%d ",a[q[l]]);
}
puts("");
}
void workmax(){
int l=,r=,i=;
for(;i<k-;i++){
while(l<=r&&a[q[r]]<=a[i]) r--;
q[++r]=i;
}
for(;i<n;i++){
if(q[l]==i-k) l++;
while(l<=r&&a[q[r]]<=a[i]) r--;
q[++r]=i;
printf("%d ",a[q[l]]);
}
puts("");
}
int main(){
while(scanf("%d%d",&n,&k)==){
for(int i=;i<n;i++)
scanf("%d",&a[i]);
workmin();
workmax();
}
}