滑动窗口
https://www.acwing.com/problem/content/156/
思考:
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++;
// 较小的值入队
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++;
// 较小的值入队
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;
}