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

题目描述

给定一个长度为

n

的数组

a

和一个长度为

k

的滑动窗口，窗口从数组的最左端滑动到最右端。每次窗口滑动时，输出窗口中的最小值和最大值。

解题思路

这道题的核心是高效地维护滑动窗口中的最值。直接暴力枚举每个窗口的最值会导致时间复杂度为

O(n \cdot k)

，无法通过本题。因此，我们需要使用单调队列来优化。

单调队列的核心思想

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

移除队尾元素：
- 当新元素加入队列时，如果新元素破坏了队列的单调性，则从队尾移除一些元素，直到队列重新满足单调性。
移除队首元素：
- 当队首元素已经不在当前窗口范围内时，将其从队首移除。

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

单调队列的应用场景

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

滑动窗口的最值问题：
- 给定一个数组和一个固定大小的窗口，求每个窗口中的最大值或最小值。
优化动态规划问题：
- 在某些动态规划问题中，单调队列可以用于优化状态转移方程，减少时间复杂度。

单调队列的实现细节

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

维护单调递增队列

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

代码实现

CPP

#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;
}

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

文章操作

题目描述

解题思路

单调队列的核心思想

单调队列的应用场景

单调队列的实现细节

维护单调递增队列

代码实现

相关推荐

评论

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