154. 滑动窗口
题目链接：154. 滑动窗口 - AcWing题库
1、暴力枚举
窗口大小为k
序列长为n
以求最小值为例
f[i] 表示以i结尾的窗口中的最小值
f[i] = min(a[j]) , i - k + 1 <= j <= i
for: i = 1 ~ n
for: j = i - k + 1 ~ i
f[i] = min(a[j])
2、单调队列 用数组模拟队列
参考视频：411【模板】单调队列 滑动窗口最值_哔哩哔哩_bilibili
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
int q[N], a[N]; //q队列存储元素的下标 方便判断对头出队 a存储数组元素
int main()
{
int n, k;
cin >> n >> k;
for(int i = 1; i <= n; i++)
cin >> a[i];
//维护窗口最小值
int h = 1, t = 0;
for(int i = 1; i <= n; i++)
{
while(h <= t && a[q[t]] >= a[i]) t--; //队尾出列(队列不空 h <= t 且新元素更优 a[q[t]] > a[i])
q[++t] = i; //队尾入队 (存储下标 方便判断队头出队)
if(q[h] < i - k + 1) h++; //队头出列 (队头元素滑出窗口)
if(i >= k) //使用最值
cout << a[q[h]] << " ";
}
//维护窗口最大值
h = 1, t = 0;
for(int i = 1; i <= n; i++)
{
while(h <= t && a[q[t]] <= a[i]) t--;
q[++t] = i;
if(q[h] < i - k + 1) h++;
if(i >= k)
cout << a[q[h]] << " ";
}
return 0;
}
其他细节问题：
1、h, t的初始化是与数组第一个值下标有关的：
h≤数组第一个下标 （如数组从0开始，h≤0；数组从1开始，h≤1，可以是1/0/-1等等）
2、对于数组第一个值下标从0还是从1开始,还会影响输出时的if判断,需要对应修改:
下标从0开始，就是i>=k-1，因为第一个窗口为0 1 2；
下标从1开始，就是i>=k，因为首个窗口是1 2 3
3、维护最小值就是维护窗口内的升序子序列， 维护最大值就是维护窗口内的降序子序列