题解 P2032 【扫描 / 滑动窗口】

1. 题目简述

给定一个长度为 $n$ 的序列和一个长度为 $k$ 的窗口。窗口从左向右滑动，每次移动一个单位。我们需要求出每次移动后，窗口内 $k$ 个数中的最大值。

数据范围： $1 \leq k \leq n \leq 2 \times 10^6$ 。

2. 思路分析

暴力法（不可行）

最朴素的想法是每移动一次窗口，就遍历窗口内的 $k$ 个元素寻找最大值。

时间复杂度： $O(n \times k)$ 。
结果： 当 $n=2 \times 10^6, k \approx n/2$ 时，运算量达到 $10^{12}$ 级别，绝对会 TLE (超时)。

优先队列 / 线段树（勉强可行但慢）

使用大根堆（优先队列）或者线段树维护区间最大值。

时间复杂度： $O(n \log k)$ 或 $O(n \log n)$ 。
结果： 虽然优于暴力，但对于 $2 \times 10^6$ 的数据量，带 $\log$ 的做法可能会因为常数过大而卡在时间限制边缘，且代码实现相对复杂。

单调队列（最优解）

我们需要维护一个双端队列 (Deque)，队列中存放的是原数组的下标。我们保持队列中的元素对应的数值是单调递减的。

核心逻辑（名言）：

“如果一个选手比你小，还比你强（数值大），那你就可以退役了。”

具体操作步骤： 遍历数组，对于每一个新加入的元素 a[i]：

去尾（维护单调性）： 检查队尾元素。如果队尾元素对应的数值 $\le$ 新元素 a[i]，说明队尾元素既比 a[i] 出现得早，又没有 a[i] 大，它永远不可能成为最大值了。直接弹出队尾，循环直到队列为空或队尾元素 $> a[i]$ 。
入队： 将当前下标 $i$ 放入队尾。
删头（移除过期元素）： 检查队头元素。如果队头下标 $idx < i - k + 1$ （即队头已经滑出了当前窗口的左边界），将其弹出。
记录答案： 只要 $i \ge k$ （窗口已形成），队头元素对应的数值 a[q.front()] 就是当前窗口的最大值。

时间复杂度： $O(n)$ 。因为每个元素最多进队一次、出队一次。

3. 样例推演

输入：n=5, k=3，数组：1 5 3 4 2

i	当前元素	队列操作 (存下标)	队列状态 (对应值)	队头是否过期?	输出 (Max)
1	1	1入队	`{1}`	否	-
2	5	1 < 5, 1出队; 5入队	`{5}`	否	-
3	3	3 < 5, 直接入队	`{5, 3}`	否	5
4	4	3 < 4, 3出队; 4 < 5, 4入队	`{5, 4}`	否	5
5	2	2 < 4, 直接入队	`{5, 4, 2}`	5的下标是2，当前窗口范围[3,5]，下标2过期，弹出	4

最终输出：5 5 4。

4. AC 代码

cpp

#include <iostream>
#include <deque>
#include <vector>

using namespace std;

// 定义最大范围，稍微大一点防止越界
const int MAXN = 2000005;
int a[MAXN];

int main() {
    // 开启 I/O 加速，数据量 2e6 必须加，否则 IO 会超时
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int n, k;
    if (!(cin >> n >> k)) return 0;

    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
    }

    // 单调队列，存储的是数组的下标
    deque<int> q;

    for (int i = 1; i <= n; ++i) {
        // 1. 维护单调递减性：
        // 如果队尾对应的元素 <= 当前元素，说明队尾元素没用了，弹出
        while (!q.empty() && a[q.back()] <= a[i]) {
            q.pop_back();
        }

        // 2. 入队
        q.push_back(i);

        // 3. 移除过期元素
        // 当前窗口范围是 [i-k+1, i]
        // 如果队头下标 < i-k+1，说明已经在窗口左边了
        if (q.front() < i - k + 1) {
            q.pop_front();
        }

        // 4. 输出答案
        // 当 i >= k 时，窗口才完全形成，开始输出
        if (i >= k) {
            cout << a[q.front()] << "\n";
        }
    }

    return 0;
}

5. 总结

关键点：时刻维护队列的单调性（从大到小）。
注意：队列中存储下标而不是数值，因为我们需要通过下标判断元素是否“过期”。
坑点：数据量达到 $2 \times 10^6$ ，C++ 必须使用 ios::sync_with_stdio(false) 或者 scanf/printf，否则会 TLE。

扫描

目录