POJ.2823 Sliding Window

1.Problem
2823 -- Sliding Window (poj.org)

2.Idea
Using Deque

3.Source

 const int N = 1000006;  
 //////////////////////////////  
 int n, k;  
 int a[N];  
 int mn[N], mx[N];  
 int deq[N];  
 void solve()  
 {  
      scanf("%d%d", &n, &k);  
      REP(i, n) scanf("%d", &a[i]);  
      //MIN values  
      int s = 0, t = 0;  
      REP(i, n) {  
           while (s < t && a[deq[t - 1]] >= a[i]) t--;  
           deq[t++] = i;  
           if (i - k + 1 >= 0) {  
                mn[i - k + 1] = a[deq[s]];  
                if (deq[s] == i - k + 1) s++;  
           }  
      }  
      REP(i, n - k + 1) {  
           printf("%d%c", mn[i], i == n - k ? '\n' : ' ');  
      }  
      //MAX Values  
      s = 0, t = 0;  
      REP(i, n) {  
           while (s < t && a[deq[t - 1]] <= a[i]) t--;  
           deq[t++] = i;  
           if (i - k + 1 >= 0) {  
                mx[i - k + 1] = a[deq[s]];  
                if (deq[s] == i - k + 1) s++;  
           }  
      }  
      REP(i, n - k + 1) {  
           printf("%d%c", mx[i], i == n - k ? '\n' : ' ');  
      }  
 }