【单调队列】poj 2823 Sliding Window

【题意】

给定一个长度为n的序列，求长度为k的滑窗内的最大值和最小值

【思路】

裸的单调队列
注意用C++提交，不然会T，orz我用G++T了好长时间

【AC】

 1 //#include<bits/stdc++.h>
 2 #include<iostream>
 3 #include<cstdio>
 4 #include<string>
 5 #include<cstring>
 6 #include<algorithm>
 7 #include<cmath>
 8 using namespace std;
 9 typedef long long ll;
10 int n,k;
11 const int maxn=1e6+2;
12 int a[maxn];
13 int mx[maxn];
14 int mn[maxn];
15 struct node
16 {
17     int x;
18     int pos;
19 }q[maxn];
20 void solve()
21 {
22     //mx 
23     int head=1;int tail=0;
24     for(int i=1;i<=n;i++)
25     {
26         while(tail>=head&&q[tail].x<=a[i]) tail--;
27         q[++tail].x=a[i];q[tail].pos=i;
28         while(q[head].pos<=i-k) head++;
29         if(i>=k) mx[i]=q[head].x;
30     }
31     //mn
32     head=1;tail=0;
33     for(int i=1;i<=n;i++)
34     {
35         while(tail>=head&&q[tail].x>=a[i]) tail--;
36         q[++tail].x=a[i];q[tail].pos=i;
37         while(q[head].pos<=i-k) head++;
38         if(i>=k) mn[i]=q[head].x;
39     }
40     for(int i=k;i<=n;i++)
41     {
42         if(i!=n) printf("%d ",mn[i]);
43         else printf("%d",mn[i]); 
44     }
45     puts("");
46     for(int i=k;i<=n;i++)
47     {
48         if(i!=n) printf("%d ",mx[i]);
49         else printf("%d",mx[i]); 
50     }
51     puts("");
52 }
53 int main()
54 {
55     while(~scanf("%d%d",&n,&k))
56     {
57         for(int i=1;i<=n;i++)
58         {
59             scanf("%d",&a[i]);
60         }
61         solve();
62     }
63     return 0;
64 }

单调队列