题目描述
详情见AcWing.154滑动窗口
样例
8 3
1 3 -1 -3 5 3 6 7
-1 -3 -3 -3 3 3 //这一行是每个窗口的最小值
3 3 5 5 6 7 //这一行是每个窗口的最大值
数组模拟队列的单调队列解法
闫总说过单调队列与单调栈的使用情况极为受限,基本遇到单调队列或者单调栈的题就直接记下来就可以了。
这道题也算一个单调队列的经典题,之后在遇到其他的问题要么直接模板照搬,要么转化一下在照搬。
但是单调队列的思路还是很重要(清奇)的。
思路
首先了解什么是滑动窗口吧
图中下标0,1,2就构成了一个长度为3的窗口,之后假定窗口的长度一直为3,当开始滑动的时候,窗口要保持窗口长度一直为3,例如整个窗口向右滑动一个距离,就变为了1,2,3。这就是滑动窗口,滑动时长度必须一致保持不变。
之后假定有一个滑动窗口,里面有两个下标i
和j
,并且有i < j
。
以求滑动窗口中最大值为例
若有nums[i] <= nums[j]
的条件,并且前文提到i < j
,我们所求的是滑动窗口的之中的最大值,那么i
下标对应的元素还有存在的意义吗?
两种情况:
①:如果当新进入了元素,j
下标对应的元素还真就是最大值,那么就直接有了最大值了,和i
下标对应的元素没有关系。
②:如果当新进入了元素,j
下标对应的元素是否为最大值还有待商榷,那么与新进入的元素进行比较也就是只有j
对应的元素,轮不到i
对应元素进行比较。因为num[i] < nums[j]
,若连j
对应的元素都小,那么i
对应的元素就更不可能成为最大值了。
综上所述,只要出现该种情况,i
对应的元素就可以直接删去。
假象一个队列,第一个元素入队,当第二个元素入队的时候,与队尾(第一个元素)元素进行比较,若第二元素 >= 第一元素
,队尾元素出队,第二个元素入队。若第二元素 < 第一元素
,说明第一元素(队尾元素)还有保留下来的必要,第二元素直接入队即可。
完成整个过程中单调队列中保存的数据都是单调递减的,在队头取到最大值,直接输出队头就可以获得最大值了。
下面对代码进行注释
C++ 代码
#include <iostream>
using namespace std;
const int N = 1000010;
//a[N]数组就是输入的原型数组
//q[N]数组是保存单调队列的数组,但是是通过保存下标来保存单调队列的。
int a[N],q[N],hh,tt = -1;
//hh是单调队列的队头,tt是单调队列的队尾
int main ()
{
int n,k;
cin >> n >> k;
for(int i = 0 ; i < n ; i++)
{
cin >> a[i]; //向原型数组中录入数据
if(i - k + 1 > q[hh]) hh++;
//这里很重要,i-k+1是什么?i - k + 1 是滑动窗口的做左侧的坐标。这个坐标要是大于q[hh]说明q数组队头元素已经出了窗口之外了,也就是取不到了直接出队就行了
while(hh <= tt && a[i] <= a[q[tt]]) tt--;
//这里在求最小值,a[i] <= a[q[tt]]就是代表只要队尾的元素大于a[i]就出队,因为求的是最小值,所以大于的就可以直接出对了,反正取最小值也轮不到他们
q[++tt] = i;
if(i + 1 >= k) cout << a[q[hh]] << " ";
//i + 1代表什么?i + 1就是原型数组的实际长度,只要实际长度大于k了说明,原型数组中最起码可以出现一个滑动窗口了,就可以开始输出值了
}
//求最大值思路类似,改个判断就行了
cout << endl;
hh = 0;
tt = -1;
for(int i = 0 ; i < n ; i++)
{
if(i - k + 1 > q[hh]) hh++;
while(hh <= tt && a[i] >= a[q[tt]]) tt--;
q[++tt] = i;
if(i + 1 >= k) cout << a[q[hh]] << " ";
}
return 0;
}
我觉的真的蛮难的,只能拿来人家代码进行注释理解了…
在此万分感谢闫总讲解与 @Hasity大佬的代码!
佬
%%%