AcWing 154. 滑动窗口
原题链接
简单
作者:
社会腐败分子
,
2020-03-13 23:34:28
,
所有人可见
,
阅读 622
这个题是滑动窗口
我想了很久很久很久 就是脑子里不确定这个算法为什么是正确的
我的疑惑主要有两点
一是 这个队首 一定会有元素吗
二是 这个队首的元素 一定是 我这个滑动窗口内的吗
三是 我输出的元素 刚好是 每一个滑动窗口中的最小的吗 也就是 我输出的队首是正确的吗
我一开始 是在 hh<=tt 这么找思路
后来发现 跟这个就没关系 这条语句 只是在确定 我队列里得有元素
最主要的一句话是
if(i>=k-1) printf("%d ",a[q[hh]]);
这句话的意思是 当我的i 大于等于窗口值的时候 输出队首
也就可以这样理解
将原数组 分成两部分
一是 0-k-1
二是 k到n-1
什么意思呢 就是你在 0 到k-1 内瞎折腾 弄出一个最小值来 我们假设 下标是j
我们假设现在队列里存在 j-j+r个元素
然后我们 i 到k-1了 输出 队首 这一定是 前k个数中的最小的
i=k
然后考虑最一般的情况
我们0到k-1中最小的数是 aj
然后
这个aj 要么被后来者代替 然后变成 aj+x
因为
分成两个区间后 每次这个aj 管的就是
从aj 到 aj+k-1 这个窗口
要是i 在这里面 就输出aj
不在 就把aj弹出就好了