POJ 2823 单调队列

题意：

n个数的序列， k大小的区间

如题目中的图依次选择区间，得到每个区间的最值

第一行输出所有区间的最小值

第二行输出所有区间的最大值

#include<stdio.h>#define N 1000005int Q1[N], Q2[N];//Q1递增int sum[N];int Stack1[N],top1,Stack2[N],top2;int main(){int n,k;while(~scanf("%d%d",&n,&k)){int front1 = 0, front2 = 0;int rear1  = 0, rear2  = 0;int last1 = 0, last2 = 0;top1 = top2 = 0;for(int i = 1; i<= n;i++){scanf("%d",&sum[i]);while(front1<rear1 && sum[ Q1[rear1-1] ]>=sum[i]) rear1--;Q1[rear1++] = i;while(front2<rear2 && sum[ Q2[rear2-1] ]<=sum[i]) rear2--;Q2[rear2++] = i;while(i - Q1[front1] >= k)front1++;while(i - Q2[front2] >= k)front2++;if(i >= k){Stack1[top1++] =sum[ Q1[front1] ];Stack2[top2++] =sum[ Q2[front2] ];}}for(int i = 0; i <top1-1;i++)printf("%d ",Stack1[i]);printf("%d\n",Stack1[top1-1]);for(int i = 0; i <top2-1;i++)printf("%d ",Stack2[i]);printf("%d\n",Stack2[top2-1]);}return 0;}