「一本通 5.5 例 1」滑动窗口

题目描述

给定长度 $N$ 的整数序列与窗口长度 $K$ （ $1 \le K \le N \le 10^6$ ， $|a_i| \le 2 \times 10^9$ ）。窗口每次右移一位，对每个位置求窗口内最小值和最大值：第一行输出全部最小值，第二行输出全部最大值，数字间单空格分隔。样例输入 8 3 换行 1 3 -1 -3 5 3 6 7，样例输出 -1 -3 -3 -3 3 3 换行 3 3 5 5 6 7。

思路

相邻窗口只差一进一出，用单调队列只保留下标：入队前从队尾弹掉被新元素支配的下标，再从队首弹掉已滑出窗口的下标，队首即为当前窗口最值。最小值、最大值各扫一遍，每个下标进出队各一次，总复杂度 $O(N)$ 。

参考代码

Python 版：

python

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
43
44
45
46
47
48
49
50
51
52
53
54
55
56#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-09-30 20:52
# update_at: 2026-10-04 11:43

import sys
from collections import deque

PART = 100_000  # 输出分块大小：整行 join 会同时生成上百万个临时 str，分块后峰值内存大幅下降


def window_extremes(a: list[int], k: int, want_max: bool) -> list[int]:
    """单调队列求每个长为 k 的窗口的最值：want_max=False 求最小值，True 求最大值。

    队列里只保留下标，且对应值保持单调，队首就是当前窗口的最值候选。
    """
    # 队尾保留条件：只有新元素不比队尾优才留着队尾；两个方向共用同一段扫描逻辑
    # 求最大时队列递减（保留「不更大」的队尾），求最小时队列递增（保留「不更小」的队尾）
    keep_tail = (lambda new, old: new <= old) if want_max else (lambda new, old: new >= old)
    dq: deque[int] = deque()
    out: list[int] = []
    for i, x in enumerate(a):
        while dq and not keep_tail(x, a[dq[-1]]):
            dq.pop()                      # 队尾被新元素压过，窗口右移后它只会更旧，永远出局
        dq.append(i)
        if dq[0] <= i - k:                # 队首已滑出窗口左边界
            dq.popleft()
        if i >= k - 1:                    # 第一个完整窗口形成，之后每步产出一个答案
            out.append(a[dq[0]])
    return out


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    try:
        n = next(data)                     # 数组长度
    except StopIteration:
        return
    k = next(data)                         # 窗口长度
    a = [next(data) for _ in range(n)]     # 整个输入序列

    # 按题面顺序：第一行最小值、第二行最大值；算完一行分块写出，临时 str 列表不整行堆积
    write = sys.stdout.write
    for want_max in (False, True):
        ext = window_extremes(a, k, want_max)
        for start in range(0, len(ext), PART):
            if start:                     # 块间补一个空格，整行仍是单空格分隔、末尾无空格
                write(" ")
            write(" ".join(map(str, ext[start : start + PART])))
        write("\n")


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-06 00:54
 * update_at: 2026-10-06 00:54
 */
// main.cpp：单调队列求滑动窗口最值，队尾淘汰被支配的下标、队首弹出过期下标。
#include <cstdio>

typedef long long ll;

const int MAXN = 1000005; // N 最大 10^6，数组多开几位留余量

ll a[MAXN];      // a[i] 表示第 i 个数（下标从 0 开始）
int dq[MAXN];    // 单调队列，存下标，队列里对应的 a 值保持单调
ll ans[MAXN];    // ans 暂存每个窗口的最值，按窗口顺序排列
int head, tail;  // dq 的队首下标与队尾后一位，区间为 [head, tail)

// 扫描整个序列，求每个长度为 k 的窗口的最值并写入 ans。
// want_max 为真求最大值（队列值递减），为假求最小值（队列值递增）。
void window_extremes(int n, int k, bool want_max) {
    head = 0;
    tail = 0;
    int cnt = 0; // 已经产出的答案个数
    for (int i = 0; i < n; i++) {
        // 队尾淘汰：新元素不劣于队尾时，队尾更早过期且不会更优，可以丢弃
        while (head < tail) {
            bool keep;
            if (want_max) {
                keep = a[dq[tail - 1]] > a[i];
            } else {
                keep = a[dq[tail - 1]] < a[i];
            }
            if (keep) {
                break;
            }
            tail--;
        }
        dq[tail] = i;
        tail++;
        // 队首过期：下标已滑出窗口左边界，弹出
        if (dq[head] <= i - k) {
            head++;
        }
        // 第一个完整窗口形成后，每步输出队首对应的最值
        if (i >= k - 1) {
            ans[cnt] = a[dq[head]];
            cnt++;
        }
    }
}

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

    // 第一行最小值
    window_extremes(n, k, false);
    int total = n - k + 1;
    for (int i = 0; i < total; i++) {
        if (i > 0) {
            printf(" ");
        }
        printf("%lld", ans[i]);
    }
    printf("\n");

    // 第二行最大值，复用同一段扫描
    window_extremes(n, k, true);
    for (int i = 0; i < total; i++) {
        if (i > 0) {
            printf(" ");
        }
        printf("%lld", ans[i]);
    }
    printf("\n");
    return 0;
}

「一本通 5.5 例 1」滑动窗口

目录

题目描述

思路

参考代码