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

AFO_kunkun127 · 2025-03-06 13:32:06 · 题解

题目描述

给定一个长度为 n 的数组 a 和一个长度为 k 的滑动窗口，窗口从数组的最左端滑动到最右端。每次窗口滑动时，输出窗口中的最小值和最大值。

解题思路

这道题的核心是高效地维护滑动窗口中的最值。直接暴力枚举每个窗口的最值会导致时间复杂度为 O(n \cdot k) ，无法通过本题。因此，我们需要使用单调队列来优化。

单调队列的核心思想

单调队列通过以下两个操作来维护队列的单调性：

1. 移除队尾元素：

   • 当新元素加入队列时，如果新元素破坏了队列的单调性，则从队尾移除一些元素，直到队列重新满足单调性。

2. 移除队首元素：

   • 当队首元素已经不在当前窗口范围内时，将其从队首移除。

通过这两个操作，单调队列能够始终维护窗口内的最值或其他性质。

单调队列的应用场景

单调队列常用于解决以下问题：

1. 滑动窗口的最值问题：

   • 给定一个数组和一个固定大小的窗口，求每个窗口中的最大值或最小值。

2. 优化动态规划问题：

   • 在某些动态规划问题中，单调队列可以用于优化状态转移方程，减少时间复杂度。

单调队列的实现细节

以下以滑动窗口的最小值为例，详细说明单调队列的实现过程。

维护单调递增队列

• 目标：维护一个单调递增的队列，队首元素始终是当前窗口的最小值。
• 操作：
  1. 当新元素加入队列时，从队尾移除所有比新元素大的元素，以保持队列的单调递增性。
  2. 当队首元素已经不在当前窗口范围内时，将其从队首移除。
  3. 队首元素即为当前窗口的最小值。

代码实现

#include <bits/stdc++.h>
using namespace std;

int a[1000005], q[1000005];

int main()
{
    int n, k;
    cin >> n >> k;
    for (int i = 1; i <= n; i++) cin >> a[i];
    int head = 1, tail = 0;
    for (int i = 1; i <= n; i++)
    {
        if (head <= tail && q[head] < i - k + 1) head++;
        while (head <= tail && a[q[tail]] > a[i]) tail--;
        q[++tail] = i;
        if (i >= k) cout << a[q[head]] << ' ';
    }
    cout << endl;
    head = 1, tail = 0;
    for (int i = 1; i <= n; i++)
    {
        if (head <= tail && q[head] < i - k + 1) head++;
        while (head <= tail && a[q[tail]] < a[i]) tail--;
        q[++tail] = i;
        if (i >= k) cout << a[q[head]] << ' ';
    }
    cout << endl;
    return 0;
}