POJ2823(Sliding Window)

经典单调队列题。
View Code
 1 #include <stdio.h>
 2 #define N 1000005
 3 int a[N];
 4 int q[N],front,rear;
 5 int main()
 6 {
 7     int i,n,k;
 8     while(~scanf("%d%d",&n,&k))
 9     {
10         for(i=0;i<n;i++)    scanf("%d",&a[i]);
11         front=rear=0;
12         for(i=0;i<n;i++)
13         {
14             while(front<rear&&a[i]<=a[q[rear-1]])  rear--;
15             q[rear++]=i;
16             while(i-q[front]+1>k)   front++;
17             if(i==k-1)    printf("%d",a[q[front]]);
18             else if(i>k-1)    printf(" %d",a[q[front]]);
19         }
20         printf("\n");
21         front=rear=0;
22         for(i=0;i<n;i++)
23         {
24             while(front<rear&&a[i]>=a[q[rear-1]])  rear--;
25             q[rear++]=i;
26             while(i-q[front]+1>k)   front++;
27             if(i==k-1)    printf("%d",a[q[front]]);
28             else if(i>k-1)    printf(" %d",a[q[front]]);
29         }
30         printf("\n");
31     }
32     return 0;
33 }