求m区间内的最小值

GitHub跳转原题关系图返回列表

用单调队列维护当前位置前 m 个数的最小值，注意先输出再插入当前元素。

OJ: luogu

题目 ID: P1440

难度:普及

标签:单调队列滑动窗口数据结构

创建: 2026-06-22 23:14

更新: 2026-08-09 06:46

后置题目
luogu P2216[HAOI2007] 理想的正方形B 的两遍扫描都直接复用 A 的一维滑动窗口单调队列取最值这一步（弹过期后队头即窗口最值），先逐行再逐列把二维正方形窗口拆成两次一维，再叠加 A 未教的行列两级拆解与 max-min 差值目标。luogu P2627[USACO11OPEN] Mowing the Lawn GB 把 A 的单调队列取窗内最值步骤用于 dp[j-1]-S[j] 的滑窗最大值，逐断点转移求最大效率和luogu P1725琪露诺B 的转移优化复用 A 的滑动窗口单调队列取最值这一步（过期前驱弹出后队头即窗口内 dp 最大位置），把 O(nR) 前驱枚举压成 O(n)，再叠加 A 未教的 dp 转移设计与最后一步可越过 N 的答案收集。

目录

  1. 题意
  2. 思路
  3. 代码
  4. 复杂度
  5. 总结

题意

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

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

思路

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

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

cpp
#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)O(nm)，而 n 可以达到 2 * 10^6，必须优化。

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

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

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

代码

cpp
#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)，每个下标最多入队和出队一次。

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

总结

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