求m区间内的最小值

题意

给定一个长度为 n 的数列。对每个位置 i，输出它前面最多 m 个数中的最小值；如果前面没有数，输出 0。

也就是求区间 [max(1, i-m), i-1] 的最小值。

思路

朴素做法是对每个 i 往前枚举最多 m 个数，直接找最小值。

先看一个可以直接验证想法的朴素解：

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

// brute.cpp：直接枚举每个位置前面的 m 个数，只适合小数据对拍。

const int MAXN = 505;

int n, m;
int a[MAXN];

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

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

    for (int i = 1; i <= n; i++) {
        int left = max(1, i - m);
        if (left > i - 1) {
            cout << 0 << '\n';
            continue;
        }
        int best = a[left];
        for (int j = left + 1; j <= i - 1; j++) {
            best = min(best, a[j]);
        }
        cout << best << '\n';
    }

    return 0;
}

朴素做法最坏是 $O(nm)$ ，而 n 可以达到 2 * 10^6，必须优化。

这是一个标准滑动窗口最小值。维护一个单调队列，队列里存下标，并保证：

下标从队头到队尾递增；
对应的数值从队头到队尾递增；
删除过期下标后，队头就是当前窗口最小值。

注意本题查询的是“第 i 项前面的 m 个数”，不包含 a[i] 本身。因此每一轮要先弹过期、输出答案，再把 i 插入队列。

代码

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

const int MAXN = 2000005;

int n, m;
int a[MAXN];
int que[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, tail = 0;
    for (int i = 1; i <= n; i++) {
        // 查询的是第 i 项前面的 m 个数，不包含 a[i] 本身。
        while (head <= tail && que[head] < i - m) {
            head++;
        }

        if (head > tail) {
            cout << 0 << '\n';
        } else {
            cout << a[que[head]] << '\n';
        }

        // 把 a[i] 放进队列，供后面的元素查询。
        while (head <= tail && a[que[tail]] >= a[i]) {
            tail--;
        }
        tail++;
        que[tail] = i;
    }

    return 0;
}

复杂度

时间复杂度 $O(n)$ ，每个下标最多入队和出队一次。

空间复杂度 $O(n)$ 。

总结

单调队列题的关键是明确窗口边界。本题窗口是 [i-m, i-1]，所以当前元素必须在输出后再入队。

求m区间内的最小值

目录

题意

思路

代码

复杂度

总结