题解：P1886 滑动窗口 /【模板】单调队列

mazhenhao0235 · 2025-03-05 22:22:58 · 题解

题目传送门

题目分析

题目要求我们解决一个滑动窗口的问题。给定一个长度为 n 的数组 a ,一个窗口大小 k ，我们需要找到每个窗口中的最小值和最大值，并输出它们。

滑动窗口问题的核心是：在数组上滑动一个固定大小的窗口，每次移动窗口时，快速求出窗口内的最小值或最大值。

解题思路

为了高效地解决这个问题，我们可以使用单调队列来维护窗口中的最小值和最大值。单调队列的核心思想是保持队列中的元素单调递增或单调递减，从而快速获取窗口中的最小或最大值。

为什么用单调队列？

暴力解法的时间复杂度是 O(nk) ，即每次移动窗口时遍历窗口内的所有元素求极值。这种方法在 n 和 k 较大时会超时。

单调队列可以将时间复杂度优化到 O(n) ，因为每个元素最多入队和出队一次。

实现步骤

1.找最小值

• 初始化
  设置一个队列 q ，用于存储数组元素的索引。 head 和 tail 分别表示队列的头部和尾部

• 遍历数组
  移除过期元素：如果队列头部的元素已经不在当前窗口范围内（即 q[head] + k - 1 < i ），则将其从队列中移除。
  维护单调性：如果队列尾部的元素大于等于当前元素 a[i] ，则将其从队列中移除，直到队列重新满足单调递增的性质。
  插入当前元素：将当前元素的索引 i 插入队列尾部。 输出最小值：如果当前窗口大小已经达到 k ，则输出队列头部元素对应的值 a[q[head]] 。

2.找最大值

• 初始化
  重新初始化队列 q , head 和 tail 。
• 遍历数组
  移除过期元素：如果队列头部的元素已经不在当前窗口范围内（即 q[head] + k - 1 < i） ，则将其从队列中移除。
  维护单调性：如果队列尾部的元素小于等于当前元素 a[i] ，则将其从队列中移除，直到队列重新满足单调递减的性质。
  插入当前元素：将当前元素的索引 i 插入队列尾部。
  输出最大值：如果当前窗口大小已经达到 k ，则输出队列头部元素对应的值 a[q[head]] 。

代码

#include<bits/stdc++.h>//万能头
using namespace std;
#define N 1000010
int n, a[N], q[N], head, tail, k;

int main() {
    ios::sync_with_stdio(0);//这就不说了
    cin.tie(0);
    cout.tie(0);

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

    // 找最小值
    head = tail = 0;
    for (int i = 1; i <= n; i++) {
        // 移除过期元素
        while (head <= tail && q[head] + k - 1 < i) ++head;
        // 维护队列单调递增
        while (head <= tail && a[q[tail]] >= a[i]) --tail;
        q[++tail] = i;
        // 输出当前窗口的最小值
        if (i >= k) cout << a[q[head]] << ' ';
    }
    cout << '\n';

    // 找最大值
    head = tail = 0;
    for (int i = 1; i <= n; i++) {
        // 移除过期元素
        while (head <= tail && q[head] + k - 1 < i) ++head;
        // 维护队列单调递减
        while (head <= tail && a[q[tail]] <= a[i]) --tail;
        q[++tail] = i;
        // 输出当前窗口的最大值
        if (i >= k) cout << a[q[head]] << ' ';
    }

    return 0;//好习惯
}

复杂度分析

时间复杂度
每个元素最多入队和出队一次，因此时间复杂度为 O(n) 。

空间复杂度
使用了一个队列来存储元素的索引，空间复杂度为 O(n) 。

总结

通过使用单调队列，我们可以高效地解决滑动窗口的最小值和最大值问题。单调队列的核心思想是通过维护队列的单调性，快速获取窗口中的极值。这种方法在时间复杂度上非常优秀，适用于大规模数据的处理。