POJ 2823 Sliding Window（单调队列）

题意：给定n长度的数字序列，求从前往后每k个数字中的最大值和最小值分别为多少。

题解：单调队列。（除去冗余状态）整个思路就是尽量删掉没用的数字，从队列尾部删掉价值不如当前的，从队列头部删掉序号不在该区间内的。

数组版：

 1 #include <cstdio>
 2 using namespace std;
 3 
 4 const int N=1e6+10;
 5 typedef long long ll;
 6 int n,k;
 7 ll a[N];
 8 
 9 struct node{
10     int id;
11     ll val;
12 }q[N];
13 
14 void getmin(){
15     int head=1,tail=0;
16     for(int i=1;i<=n;i++){
17         while(head<=tail&&q[tail].val>=a[i]) tail--;
18         q[++tail].val=a[i];q[tail].id=i;
19         if(i>=k){
20             while(head<=tail&&q[head].id<=i-k) head++;
21             printf("%lld ",q[head].val);
22         }
23     }
24     printf("
");
25 }
26 
27 void getmax(){
28     int head=1,tail=0;
29     for(int i=1;i<=n;i++){
30         while(head<=tail&&q[tail].val<=a[i]) tail--;
31         q[++tail].val=a[i];q[tail].id=i;
32         if(i>=k){
33             while(head<=tail&&q[head].id<=i-k) head++;
34             printf("%lld ",q[head].val);
35         }
36     }
37     printf("
");
38 }
39 
40 int main(){
41     scanf("%d%d",&n,&k);
42     for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
43     getmin();
44     getmax();
45     return 0;
46 }

View Code

deque版：

 1 #include <queue>
 2 #include <cstdio>
 3 using namespace std;
 4 
 5 const int N=1e6+10;
 6 int n,k;
 7 int a[N];
 8 deque <int> q1,q2;
 9 
10 void getmin(){
11     for(int i=1;i<=n;i++){
12         while(!q1.empty()&&a[i]<=a[q1.back()]) q1.pop_back();
13         q1.push_back(i);
14         if(i>=k){
15             while(!q1.empty()&&q1.front()<=i-k) q1.pop_front();
16             printf("%d ",a[q1.front()]);
17         }
18     }
19     printf("
");
20 }
21 
22 void getmax(){
23     for(int i=1;i<=n;i++){
24         while(!q2.empty()&&a[i]>=a[q2.back()]) q2.pop_back();
25         q2.push_back(i);
26         if(i>=k){
27             while(!q2.empty()&&q2.front()<=i-k) q2.pop_front();
28             printf("%d ",a[q2.front()]);
29         }
30     }
31     printf("
");
32 }
33 
34 int main(){
35     scanf("%d%d",&n,&k);
36     for(int i=1;i<=n;i++) scanf("%d",&a[i]);
37     getmin();
38     getmax();
39     return 0;
40 }

View Code