洛谷 P1886 滑动窗口 题解

发表于 | 分类于 | | 热度: ℃

Description

有一堆共 $n$ 个数字，一个大小为 $k$ 的窗口。窗口从左边开始向右滑动，每次滑动一个单位，求每次滑动后窗口中的最大值和最小值。

数据范围：$n≤10^6$

Solution

全部摘抄自洛谷题解区 $@hankeke$ 的题解

样例

1
2
8 3
1 3 -1 -3 5 3 6 7

这是一道单调队列模板题。设 $q$ 为单调队列，$p$ 为对应编号。

$1.$ 由于此时队列为空，直接令 $1$ 进队。此时，$q=$ { $1$ } ,$p=$ { $1$ }。

$2.$ 现在 $3$ 面临抉择。假如把 $3$ 放进去，如果后面 $2$ 个数都比它大，那么 $3$ 在其有生之年就有可能成为最小的。此时，$q=$ { $1,3$ } $,p=$ { $1,2$ }。

$3.$ 下面出现了 $-1$。队尾元素 $3$ 比 $-1$ 大，那么只要 $-1$ 进队，$3$ 在其有生之年必定成为不了最小值，因为当下面 $3$ 被框起来，那么 $-1$ 也一定被框起来。$3$ 从队尾出队。同理，$1$ 从队尾出队。$-1$ 进队。此时 $q=$ { $-1$ } $,p=$ { $3$ }

$4.$ 出现 $-3$，同上，$-1>-3$，$-1$ 从队尾出队，$-3$ 从队尾进队。$q=$ { $-3$ } ，$p=$ { $4$ }。

$5.$ 出现 $5$，因为 $5>-3$，同 $2.$ 分析，$5$ 还是有希望的，所以 $5$ 进队。此时，$q=$ { $-3,5$ } ，$p=$ { $4,5$ }

$6.$ 出现 $3$。$3$ 先与队尾的5比较，$3<5$，按照第 $3$ 条的分析，$5$ 从队尾出队。$3$ 再与 $-3$ 比较，同 $2.$ 分析，$3$ 进队。此时，$q=$ { $-3,3$ }，$p=$ { $4,6$ }

$7.$ 出现 $6$。$6$ 与 $3$ 比较，因为 $3<6$，所以 $3$ 不必出队。由于 $3$ 以前元素都 $<3$，所以不必再比较，$6$ 进队。因为 $-3$ 此时已经在滑动窗口之外，所以 $-3$ 从队首出队。此时，$q=$ { $3,6$ }，$p=$ { $6,7$ }

$8.$ 出现 $7$。队尾元素 $6$ 小于 $7$，$7$ 进队。此时，$q=$ { $3,6,7$ }，$p=$ { $6,7,8$ }。

Code

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
37
38
39
40
41
42
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

const int N = 2000000;
int n, k, a[N], q[N], p[N];

void min_()
{
    int head = 1, tail = 0;
    for(int i = 1; i <= n; i++)
    {
        while(tail >= head && a[i] <= q[tail]) tail--;
        q[++tail] = a[i];
        p[tail] = i;
        while(p[head] <= i - k) head++;
        if(i >= k) printf("%d ", q[head]);
    }
    printf("\n");
}

void max_()
{
    int head = 1, tail = 0;
    for(int i = 1; i <= n; i++)
    {
        while(tail >= head && a[i] >= q[tail]) tail--;
        q[++tail] = a[i];
        p[tail] = i;
        while(p[head] <= i - k) head++;
        if(i >= k) printf("%d ", q[head]);
    }
}

int main()
{
    scanf("%d%d", &n, &k);
    for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
    min_(), max_();
    return 0;
}