最简单的单调队列应用吧
单调队列是指在一个队列中各个元素单调 递增(或者递减),并且各个元素的下标单调 递增。
单调队列的大体操作
进队时，将进队的元素为e，从队尾往前扫描，直到找到一个不大于e的元素d，将e放在d之后，舍弃e之后的所有元素；如果没有找到这样一个d，则将e放在队头(此时队列里只有这一个元素)。
出队时，将出队的元素为e，从队头向后扫描，直到找到一个元素f比e后进队，舍弃f之前所有的。(实际操作中，由于是按序逐个出队，所以每次只需要出队只需要比较队头)。
每个元素最多进队一次，出队一次，摊排分析下来仍然是 O(1)。
#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<stdlib.h>
#include<queue>
using namespace std;
#define N 25020
int p[N],q[N];
int main()
{
int i=,j,k,m,maxz=;
scanf("%d",&m);
while(scanf("%d",&k)!=EOF)
{
if(k==-) break;
i++;
p[i] = k;
maxz = max(maxz,k);
}
if(m>=i)
{
printf("%d\n",maxz);
return ;
}
int str=,end=;
for(j = ; j <= i ; j++)
{
while(end>=str&&p[j]>=p[q[end]])
end--;
end++;
q[end] = j;
while(q[str]<=j-m)
str++;
if(j>=m)
printf("%d\n",p[q[str]]);
}
return ;
}