滑动窗口/单调队列¶
前置知识¶
数组，用数组实现队列，单调性
目标¶
单调队列模板题
What¶
学过计算机网络的同学，都知道滑动窗口协议（Sliding Window Protocol），该协议是 TCP协议 的一种应用，用于网络数据传输时的流量控制，以避免拥塞的发生。该协议允许发送方在停止并等待确认前发送多个数据分组。由于发送方不必每发一个分组就停下来等待确认。因此该协议可以加速数据的传输，提高网络吞吐量。
滑动窗口算法其实和这个是一样的，只是用的地方场景不一样，可以根据需要调整窗口的大小，有时也可以是固定窗口大小。
滑动窗口算法在一个特定大小的字符串或数组上进行操作，而不在整个字符串和数组上操作，这样就降低了问题的复杂度，从而也达到降低了循环的嵌套深度。其实这里就可以看出来滑动窗口主要应用在数组和字符串上。
单调队列，是一种内部元素具有单调性的队列，可以解决“区间内最值”等问题。
How¶
模拟窗口，滑动。在滑动的过程中，维护窗口区间内的最值
题意：滑动窗口位于每个位置时，窗口内的最大值和最小值是多少 思考： 1.暴力怎么做 2.队列当中有没有无用的值，怎么去掉 3.删掉多余的值，构造单调性 4.有了单调性，就有了极值，就优化了问题
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
int a[N], q[N], n, k;
int hh, tt;
int main(){
cin >> n >> k;
for (int i = 0; i < n; i++) scanf("%d", &a[i]);
hh = 0, tt = -1;
for (int i = 0; i < n; i++){
// 窗口滑出去了
if (hh <= tt && i - k + 1 > q[hh]) hh++;
// 为了保证递增的单调性，从后往前，把比a[i]大的，全部弹出，然后把a[i]入队
while (hh <= tt && a[q[tt]] >= a[i]) tt--;
q[++tt] = i;
// 窗口是满的就输出,没满k宽度的时候，是不可输出的
// 队列是单调递增的，队头是窗口里的最小值
if (i - k + 1 >= 0) printf("%d ", a[q[hh]]);
}
puts("");
hh = 0, tt = -1;
for (int i = 0; i < n; i++){
// 窗口滑出去了
if (hh <= tt && i - k + 1 > q[hh]) hh++;
// 为了保证递减的单调性，从后往前，把比a[i]小的，全部弹出，然后让a[i]入队
while (hh <= tt && a[q[tt]] <= a[i]) tt--;
q[++tt] = i;
// 窗口是满的就输出,没满k宽度的时候，是不可输出的
if (i - k + 1 >= 0) printf("%d ", a[q[hh]]);
}
puts("");
return 0;
}
题单¶
总结¶
提高组入门算法