题意

输出每个固定宽度窗口的最小值。

思路

每个窗口都重新扫一遍找最小值，慢在哪里？

最坏 $M \approx N = 10^5$，共有 $N-M+1$ 个窗口，每个窗口暴力扫是 $O(M)$，总代价 $O(NM) = 10^{10}$ 必然超时。但窗口每次只挪一格：右边进一个、左边出一个，绝大部分元素没有变，全量重扫浪费了这些不变的部分。

能不能让每个元素只被"看见"有限次？

窗口滑动是确定的顺序过程。设 $a[j]$（$j > i$）晚于 $a[i]$ 进入窗口，只要 $a[j] \le a[i]$，那么 $a[j]$ 在窗口里存活的每一天，$a[i]$ 都不可能是窗口最小值；而 $a[i]$ 比 $a[j]$ 更早离开。所以在 $a[j]$ 到来那一刻，$a[i]$ 就永久失去成为答案的机会——这个淘汰不可逆，可以放心丢掉它。

如何组织"仍可能成为答案"的候选？

候选按下标递增排列；由于上面的淘汰规则，候选的值必须严格递增（出现不增就会淘汰前者）。所以维护一个"下标递增、值严格递增"的队列：新元素入队前，先把队尾所有值 $\ge$ 它的元素弹掉，再把它放到队尾。队首就是当前窗口最小值。

队首什么时候作废？

窗口的候选必须都在窗口内。当前右端是 $i$，窗口左端是 $i-M+1$，所以队首下标 $\le i-M$ 就滑出了窗口，直接弹出。队列里剩下的元素全在窗口内且值递增，队首自然是最小值。

什么时候开始输出？

第 $i$ 个元素入队后若 $i \ge M$，窗口已完整，输出队首值即可。

队列保存下标且对应值严格递增。加入新值时，队尾不小于它的元素以后不可能成为最小值，全部弹出；队首若离开窗口也弹出。形成完整窗口后，队首值就是答案。

Python 知识

• collections.deque 支持两端 $O(1)$ 删除。
• 队列存下标而非值，才能判断元素是否过期。
• enumerate(values) 同步取得窗口右端和新值。

代码

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#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100005;

int n, m;
int a[MAXN];
int q[MAXN]; // 单调队列里存下标

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

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

    int head = 1;
    int tail = 0;

    for (int i = 1; i <= n; i++) {
        // 把已经滑出窗口左端的下标弹掉。
        while (head <= tail && q[head] <= i - m) {
            head++;
        }

        // 维护队列中对应的值单调递增，这样队头就是窗口最小值。
        while (head <= tail && a[q[tail]] >= a[i]) {
            tail--;
        }

        q[++tail] = i;

        if (i >= m) {
            cout << a[q[head]] << '\n';
        }
    }

    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19import sys
from collections import deque


data = iter(map(int, sys.stdin.buffer.read().split()))
n, width = next(data), next(data)
values = [next(data) for _ in range(n)]
queue = deque()
answers = []

for i, value in enumerate(values):
    while queue and values[queue[-1]] >= value:
        queue.pop()
    queue.append(i)
    if queue[0] <= i - width:
        queue.popleft()
    if i + 1 >= width:
        answers.append(str(values[queue[0]]))
print("\n".join(answers))

复杂度

每个下标进出队各一次，时间 $O(n)$，空间 $O(m)$。

总结

固定窗口最值的标准结构是单调队列，不需要堆的懒删除和对数因子。