例题：求滑动窗口的最大最小值
给定一个大小为 n≤1e6 的数组。
有一个大小为 k 的滑动窗口，它从数组的最左边移动到最右边。
你只能在窗口中看到 k 个数字。
每次滑动窗口向右移动一个位置。更简而言之，对数组 [1 3 -1 -3 5 3 6 7] ，k = 3
| 窗口位置 | 最小值 | 最大值 |
| [1, 3, -1] -3 5 3 6 7 | -1 | 1 |
| 1, [3, -1, -3] 5 3 6 7 | -3 | 3 |
| 1, 3, [-1, -3, 5] 3 6 7 | -3 | 5 |
| 1, 3, -1, [-3, 5, 3] 6 7 | -3 | 5 |
| 1, 3, -1, -3, [5, 3, 6] 7 | 3 | 6 |
| 1, 3, -1, -3, 5, [3, 6, 7] | 3 | 7 |
最后输出
-1 -3 -3 -3 3 3
3 3 5 5 6 7这样就是一个单调队列的例题。
遍历队列中的所有元素，时间复杂度O(n*k)，1e12，明显tle，代码不贴了
优化思路与单调栈相类似，先看暴力怎么做，再看有没有元素会被删掉，再看有没有单调性。这里以最小值举例。
以窗口 1, [3, -1, -3] 5 3 6 7 求最小值为例。 只要-3存在，那么 3 和 -1 永远不会被作为答案输出。
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
int a[N], q[N];
int main()
{
ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
int n, k; cin >> n >> k;
for (int i = 0; i < n; i ++ ) cin >> a[i];
int hh = 0, tt = -1;
for (int i = 0; i < n; i ++ )
{
// 判断队头是否已经滑出窗口
if (hh <= tt && i - k + 1 > q[hh]) hh ++ ;
while (hh <= tt && a[q[tt]] >= a[i]) tt -- ;
q[ ++ tt] = i;
if (i >= k - 1) cout << a[q[hh]] << ' ';
}
cout << '\n';
hh = 0, tt = -1;
for (int i = 0; i < n; i ++ )
{
// 判断队头是否已经滑出窗口
if (hh <= tt && i - k + 1 > q[hh]) hh ++ ;
while (hh <= tt && a[q[tt]] <= a[i]) tt -- ;
q[ ++ tt] = i;
if (i >= k - 1) cout << a[q[hh]] << ' ';
}
return 0;
}代码如上
评论（0）
暂无评论