单调队列的应用：求滑动窗口中的最大值。

原题链接

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <iostream>
using namespace std;

const int N = 1e6+10;

int n,k;

int q[N], a[N];
int tt, hh;

int main() {
    scanf("%d%d", &n, &k);
    for(int i=0;i<n;i++) {
        scanf("%d", &a[i]);
    }
    hh=0, tt=-1;
    for(int i=0;i<n;i++) {
        // 队头元素已经不在滑动窗口中了，就删掉
        if(hh <= tt && q[hh] < i-k+1) hh++;
        // 如果当前元素比队尾元素小，就把队尾元素删掉
        while(hh <= tt && a[q[tt]] >= a[i]) tt--;
        // 当前元素入队
        q[++tt] = i;
        // 打印队头元素，最小值
        if(i>=k-1) printf("%d ", a[q[hh]]);
    }
    puts("");
    hh=0, tt=-1;
    for(int i=0;i<n;i++) {
        if(hh <= tt && q[hh] < i-k+1) hh++;
        while(hh <= tt && a[q[tt]] <= a[i]) tt--;
        q[++tt] = i;
        if(i>=k-1) printf("%d ", a[q[hh]]);
    }
    return 0;
}