单调队列
题目 滑动窗口
思路分析
整理一下就是几个关键点
一个原本的数组a[] 一个单调队列维护答案q[] 对头为hh=0 队尾为tt=-1
单调队列中存放的是答案所在的下标
****
保证窗口始终不大于3
使用i-k+1（窗口的左端点）去与队头元素比较（队列里放的下标 所以能比较）
若i-k+1>q[hh]则说明原本队列里的队头元素不在窗口里了 要hh++
但是这样只能保证不大于3 为了防止不断hh++使得队列没了
还得加上条件hh<=tt
所以
if (hh <= tt && i - k + 1 > q[hh])
hh ++ ;
第二点
因为队列里放的是下标
所以在对每个元素判断进而决定是否修改队列时 需要做的判断也要修改
如果新元素插入 会和队尾元素形成逆序 就tt--；
判断条件应该是a[q[tt]] 注意q里是下标 下标
同理 防止一直tt--导致队列没了 还得加上hh<=tt
while (hh <= tt && a[q[tt]] >= a[i])
tt -- ;
在对队列修改完后 要把当前元素入队
q[ ++ tt] = i;
这里也要注意 是入队下标！
第三点
什么时候有答案 答案是什么
窗口形成时才有答案 答案是对头元素
窗口形成怎么判断？ 窗口大小为3 那就i在第三位置的时候呗
if (i >= k - 1)
printf("%d ", a[q[hh]]);
如果要求窗口最大值 也是同理
只要把这里的单调递增改成单调递减即可
要改的地方只有第二步 判断部分
while (hh <= tt && a[q[tt]] <= a[i])
tt -- ;
q[ ++ tt] = i;
代码实现
#include<bits/stdc++.h>
using namespace std;
const int N=1000010;
int a[N],q[N];
int main()
{
int n,k;
cin>>n>>k;
for(int i=0;i<n;i++)
scanf("%d",&a[i]);
int hh=0,tt=-1;//队尾插入 tt=-1 q[++tt]可以保证0号位置被用
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]]);
}
cout<<endl;
//记得重置队列
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]]);
}
return 0;
}
💬 评论