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;}