poj-2823 Sliding Window

基础的单调队列，维护一个单调递增和一个单调递减队列即可。

#include
  
   
#define M 2000005
int a[M],Q[M],I[M];
int i,n,k;
void getMax() //求每个区间的最大值 维护一个单调递减的队列，则队首元素就是这个区间的最大值，如果不在范围内就队首元素加1
{
    int head=1,tail=0; //队首指针   队尾指针
    for(i=1;i
   






    =a[i])tail--; tail++; Q[tail]=a[i];I[tail]=i; } for(i=k;i<=n;i++) { while(head<=tail&&Q[tail]>=a[i])tail--; tail++; Q[tail]=a[i];I[tail]=i; while(I[head]<=i-k) head++; printf("%d ",Q[head]); } } int main() { while(scanf("%d %d",&n,&k)!=EOF) { for(i=1;i<=n;i++) scanf("%d",&a[i]); getMin(); printf("\n"); getMax(); } return 0; } 
   
  

?