专题学习1 - I - 滑动窗口

题意

给一个长度为 N 的数组，一个长为 K 的滑动窗体从最左端移至最右端，你只能看到窗口中的 K 个数，每次窗体向右移动一位，如下图：

窗口位置 最小值 最大值
[1 3 -1] -3 5 3 6 7 −1 3
1 [3 -1 -3] 5 3 6 7 −3 3
1 3 [-1 -3 5] 3 6 7 -3 5
1 3 -1 [-3 5 3] 6 7 -3 5
1 3 -1 -3 [5 3 6] 7 3 6
1 3 -1 -3 5 [3 6 7] 3 7

你的任务是找出窗体在各个位置时的最大值和最小值。

输入格式

第 1 行：两个整数 N 和 K；
第 2 行：N 个整数，表示数组的 N 个元素(≤2×10^9)；

输出格式

第一行为滑动窗口从左向右移动到每个位置时的最小值，每个数之间用一个空格分开；
第二行为滑动窗口从左向右移动到每个位置时的最大值，每个数之间用一个空格分开。

思路

单项队列模板题。

代码

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
#include <iostream>
using namespace std;
const int N = 5 + 1e6;

int a[N];
int q1[N], q2[N];

int main() {
    int n, m, hh, tt;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);

    //min_deque
    hh = 1, tt = 0;
    for (int i = 1; i <= n; i++) {
        while (hh <= tt && q1[hh] + m <= i) hh++;
        while (hh <= tt && a[i] < a[q1[tt]]) tt--;
        q1[++tt] = i;
        if (i >= m) printf("%d ", a[q1[hh]]);
    }
    cout << '\n';
    
    //max_deque
    hh = 1, tt = 0;
    for (int i = 1; i <= n; i++) {
        while (hh <= tt && q2[hh] + m <= i) hh++;
        while (hh <= tt && a[i] > a[q2[tt]]) tt--;
        q2[++tt] = i;
        if (i >= m) printf("%d ", a[q2[hh]]);
    }
    cout << '\n';
    
    return 0;
}