单调队列

 1 #include<iostream>
 2 using namespace std;
 3 
 4 const int N = 1e6 + 10;
 5 
 6 int n,k;
 7 int a[N],q[N]; //q代表单调队列
 8 
 9 int main()
10 {
11     scanf("%d%d", &n,&k);
12     for (int i = 0; i < n; i ++ ) scanf("%d", &a[i]);
13     
14     int hh = 0,tt = -1;
15     for (int i = 0; i < n; i ++ )
16     {
17         //判断队头是否已经弹出队列
18         if(hh <= tt && i - k + 1 > q[hh]) hh ++; //头出窗口 hh向前移动一格；
19         while(hh <= tt && a[q[tt]] >= a[i]) tt --; // 若不满足单调性，那么将队尾元素删除；
20         q[ ++tt] = i; //将元素添加到队尾
21         if(i >= k - 1) printf("%d ",a[q[hh]]);
22     }
23     puts(" ");
24     
25     hh = 0,tt = -1;
26     for (int i = 0; i < n; i ++ )
27     {
28         if(hh <= tt && i - k + 1 > q[hh]) hh ++;
29         while(hh <= tt && a[q[tt]] <= a[i]) tt --;
30         q[ ++tt] = i;
31         if(i >= k - 1) printf("%d ",a[q[hh]]);
32     }
33     puts(" ");
34     
35     return 0;
36 }