AcWing 154. 滑动窗口
原题链接
简单
作者:
jin_jin
,
2024-04-13 16:26:26
,
所有人可见
,
阅读 1
评论区找到的参考讲解:
https://www.bilibili.com/video/BV1H5411j7o6/?share_source=copy_web&vd_source=ced184f40ff84365ac3e626d924be602
代码:
#include <iostream>
using namespace std;
const int N = 1000010;
int q[N],a[N];//q存储下标
int main()
{
int n,k;
scanf("%d%d",&n,&k);
int head=0;
int tail=-1;
for(int i=0;i<n;i++)
{
scanf("%d",&a[i]);
}
//找最小值
for(int i=0;i<n;i++)
{
if(head<=tail&&q[head]<i-k+1) head++;
while(head<=tail&&a[i]<=a[q[tail]])
{
tail--;
}
q[++tail]=i;
if(i>=k-1)
{
cout<<a[q[head]];
if(i<n-1){
cout<<' ';
}
}
}
cout<<endl;
head=0;tail=-1;
for(int i=0;i<n;i++)
{
if( q[head]<i-k+1) head++;
while(head<=tail&&a[i]>=a[q[tail]])
{
tail--;
}
q[++tail]=i;
if(i>=k-1)
{
cout<<a[q[head]];
if(i<n-1){
cout<<' ';
}
}
}
return 0;
}