Sliding Window poj 单调队列的简单应用
/*算是单调队列入门吧。简单。根据ppt模板易得答案。*/#include <iostream>#include <stdio.h>#define maxn 1000001using namespace std;struct node{ int num,id; node(){} node(int _num,int _id) { num=_num; id=_id; }}q[maxn];node p[maxn];int a[maxn];int mmax[maxn];int mmin[maxn];int main(){ int n,k; scanf("%d%d",&n,&k); int t=0,f=0; int head=0,rear=0; int h=0,r=0; for(int i=1;i<=n;i++) { scanf("%d",&a[i]); while(head<rear&&q[rear-1].num<a[i]) rear--; q[rear++]=node(a[i],i); while(head<rear&&i-q[head].id>=k) head++; mmax[t++]=q[head].num; while(h<r&&p[r-1].num>a[i]) r--; p[r++]=node(a[i],i); while(h<r&&i-p[h].id>=k) h++; mmin[f++]=p[h].num; } printf("%d",mmin[k-1]); for(int i=k;i<t;i++) printf(" %d",mmin[i]); printf("\n"); printf("%d",mmax[k-1]); for(int i=k;i<f;i++) printf(" %d",mmax[i]); printf("\n"); return 0;}