POJ-2823-Sliding Window

　　　　Sliding Window

　　题目链接：http://poj.org/problem?id=2823

　　题目大意：给定含有n个元素的无序序列a[]，和一个整数k，要求求出a[]中每连续k个元素组成的子序列中的最小值（或最大值）。

　　算法：单调队列

　　单调队列简介：单调队列与普通队列相比，不只在队头出、队尾进，有时也在队尾进行出队。比如说维持单增的时候，新插入一个数时，向队头扫描队中的元素，如果有比这个数大的，直接出队，最后再将这个数入队。

　　比如： 1 4 3 2 5 3

　　1. 1

　　2. 1 4

　　3. 1 3

　　4. 1 2

　　5. 1 2 5

　　6. 1 2 3

 1 #include<stdio.h>
 2 #define N 1000010
 3 // C++ 能过
 4 typedef struct
 5 {
 6   int pos;     //这个数在原队列的位置
 7   int data;    //这个数的值
 8 }SQ;
 9 int a[N];
10 SQ q[N];
11 int l,r;
12 void QIn(int i)
13 {
14   while(r>l&&q[r-1].data>=a[i]) r--;
15   q[r].pos=i;  
16   q[r].data=a[i];
17   r++;
18 }
19 int QPop(int i)
20 {
21   int tmp=q[l].data;
22   if(i>=q[l].pos) l++;
23   return tmp;
24 }
25 SQ p[N];
26 int ll,rr;
27 void PIn(int i)
28 {
29   while(rr>ll&&p[rr-1].data<=a[i]) rr--;
30   p[rr].pos=i;
31   p[rr].data=a[i];
32   rr++;
33 }
34 int PPop(int i)
35 {
36   int tmp=p[ll].data;
37   if(i>=p[ll].pos) ll++;  //如果这个数要从队头出队了，就l++，如果没有，维持不变
38   return tmp;
39 }
40 int main()
41 {
42   int n,m;
43   while(~scanf("%d%d",&n,&m))
44   {
45     l=r=0;
46     ll=rr=0;
47     for(int i=0;i<n;i++)
48       scanf("%d",a+i);
49     for(int i=0;i<n&&i<m-1;i++)
50     {
51       QIn(i);
52       PIn(i);
53     }
54     if(m>n)
55     {
56       printf("%d
",QPop(0));
57       printf("%d
",PPop(0));
58       continue;
59     }
60     for(int i=m-1;i<n;i++)
61     {
62       QIn(i);
63       if(i>m-1) printf(" ");
64       printf("%d",QPop(i-m+1));
65     }
66     printf("
");
67     for(int i=m-1;i<n;i++)
68     {
69       PIn(i);
70       if(i>m-1) printf(" ");
71       printf("%d",PPop(i-m+1));
72     }
73     printf("
");
74   }
75   return 0;
76 }