「一本通 4.2 例 2」最敏捷的机器人

题目描述

给定长度为 $n$ 的序列与窗口长度 $k$ （ $1 \le k \le n \le 10^5$ ），对每个窗口 $[i, i+k-1]$ 输出最大值与最小值，共 $n-k+1$ 行。

思路

用两条单调队列（存下标）分别维护窗口最大值（值递减）与最小值（值递增）。新元素入队时从队尾弹出被支配的候选；队首下标若已滑出窗口则弹出。每个下标进出各一次，均摊 $O(1)$ ，总时间 $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#!/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 17:20
# update_at: 2026-09-30 17:20

import sys
from collections import deque
from collections.abc import Iterator


def window_extremes(arr: list[int], k: int) -> Iterator[tuple[int, int]]:
    """滑动窗口依次产出每个窗口的 (最大值, 最小值)：单调队列按淘汰时机保候选极值。

    hi/lo 存下标，值分别单调递减/递增，队首即当前窗口极值候选；
    下标只增不减，过期元素（下标 <= i-k）从队首弹掉，整体均摊 O(1)。
    """
    hi: deque[int] = deque()  # 队首最大：入队前弹掉所有不小于当前值的下标
    lo: deque[int] = deque()  # 队首最小：入队前弹掉所有不大于当前值的下标
    for i, value in enumerate(arr):
        while hi and arr[hi[-1]] <= value:
            hi.pop()
        hi.append(i)
        while lo and arr[lo[-1]] >= value:
            lo.pop()
        lo.append(i)

        expired = i - k  # 窗口左端已推进到 i-k+1，其前的下标全部过期
        if hi[0] <= expired:
            hi.popleft()
        if lo[0] <= expired:
            lo.popleft()
        if i >= k - 1:  # 首个完整窗口形成后才有答案
            yield arr[hi[0]], arr[lo[0]]


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n, k = next(data), next(data)
    arr = [next(data) for _ in range(n)]

    out = [f"{mx} {mn}" for mx, mn in window_extremes(arr, k)]
    print("\n".join(out))


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/**
 * 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:41
 * update_at: 2026-10-06 00:41
 */
#include <iostream>
using namespace std;

typedef long long ll;

const int MAXN = 1000005;

ll a[MAXN];          // 原始序列
int q1[MAXN], q2[MAXN]; // q1 维护最大值（值递减），q2 维护最小值（值递增）
int h1, t1, h2, t2;     // 队首、队尾指针

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, k;
    if (!(cin >> n >> k)) return 0;
    for (int i = 1; i <= n; ++i) cin >> a[i];

    h1 = t1 = h2 = t2 = 0; // 队列清空（下标从 1 开始存）

    for (int i = 1; i <= n; ++i) {
        // 最大值队列：队尾值 <= a[i] 则永无出头之日，弹出
        while (h1 < t1 && a[q1[t1]] <= a[i]) --t1;
        q1[++t1] = i;
        // 最小值队列：队尾值 >= a[i] 则永无出头之日，弹出
        while (h2 < t2 && a[q2[t2]] >= a[i]) --t2;
        q2[++t2] = i;

        // 队首过期：窗口左端为 i-k+1，更小的下标已滑出
        while (h1 < t1 && q1[h1 + 1] <= i - k) ++h1;
        while (h2 < t2 && q2[h2 + 1] <= i - k) ++h2;

        if (i >= k) {
            cout << a[q1[h1 + 1]] << ' ' << a[q2[h2 + 1]] << '\n';
        }
    }
    return 0;
}

「一本通 4.2 例 2」最敏捷的机器人

目录

题目描述

思路

参考代码