AcWing 154. 滑动窗口
原题链接
简单
作者:
YAX_AC
,
2024-03-29 21:18:39
,
所有人可见
,
阅读 4
#include<iostream>
using namespace std;
const int N = 1000010;
int n,k;
int a[N],q[N];//队列是存储的下标
int main()
{
cin>>n>>k;
for(int i = 0; i<n; i++) cin>>a[i];
int hh = 0,tt = -1;
for(int i = 0; i<n; i++)
{
if(q[hh] < i-k+1) hh++;//如果队列长度大于k,队头出队
while(hh<=tt && a[q[tt]] >= a[i]) tt--;//新加入的元素要比队尾的值小,即删去队尾的值,保证队列的单调递增性
q[++tt] = i;//将新加入的元素的下标入队
//只要下标大于k,前面又有保证队列长度为k的条件,所有下标大于k后就可以一直输出队头元素了
//i+1是因为元素下标是从0开始的
if(i+1>=k) cout<<a[q[hh]]<<' ';
}
puts("");
hh = 0,tt = -1;
for(int i = 0; i<n; i++)
{
if(q[hh] < i-k+1) hh++;//如果队列长度大于k,队头出队
while(hh<=tt && a[q[tt]] <= a[i]) tt--;//新加入的元素要比队尾的值小,即删去队尾的值,保证队列的单调递增性
q[++tt] = i;//将新加入的元素的下标入队
//只要下标大于k,前面又有保证队列长度为k的条件,所有下标大于k后就可以一直输出队头元素了
if(i+1>=k) cout<<a[q[hh]]<<' ';
}
return 0;
}