AcWing 154. 滑动窗口
原题链接
简单
作者:
执笔执念
,
2021-08-09 00:32:07
,
所有人可见
,
阅读 219
#include<iostream>
using namespace std;
const int N = 1000010;
//a是我们原来的值
//q是我们的单调队列
int a[N],q[N];
int main(){
int n,k;
scanf("%d%d",&n,&k);
for(int i = 0;i < n;i++) scanf("%d",&a[i]);
int hh = 0,tt = -1;
for(int i =0;i < n;i++){
//判断队头是否划出窗口
//队列存的其实是下标
//先判断队列是否为空,
//当前终点是i那么起点就是i - k + 1
//我的理解是:
//判断队头是否在窗口内部(0~2),并且队尾不超过i - k + 1(实质也是0~2这个长度区间内)
//这里的q[hh] 保存的就是你的单调队列的头 下标
//这里if每次挪一次
if(hh <= tt && i - k + 1 > q[hh]) hh++; // 入队 //判断当头的下标小于尾,尾的下标比头大 则头往前挪
//这段代码是这题 降低复杂度的 核心(core)操作(operate)
//当i下标之前的(a[q[tt]])如果有比a[i]当前值大的话 就干掉下标tt这个比a[i]大的值
//as a[j] > a[i] && i > j,那么a[j]就毫无用武之地(找最小值,最大值就反过来) 因为a[j] 不但大于 a[i] 活得还比a[i]短 hh
//so t--
while(hh <= tt && a[q[tt]] >= a[i]) tt--;//出队
//注意这个是从前 k 个数输出的,所以
//不足 k 就不必输出了
//这里进行特判一下,
//前k个数就输出出来
q[++tt] = i;//当前的数字插入队列
if(i >= k - 1) 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;
if(i >= k - 1) printf("%d ",a[q[hh]]);
}
puts("");
return 0;
}