AcWing 154. 滑动窗口
原题链接
简单
作者:
术
,
2021-01-06 17:36:53
,
所有人可见
,
阅读 278
#include <iostream>
using namespace std;
const int N=1000005;
int que[N];//存下标 要么没法判断元素是否出队
int a[N];
int hh=0,tt=-1;
int main()
{
int n,k,x;
cin>>n>>k;
for(int i=0;i<n;i++){
cin>>a[i];
}
for(int i=0;i<n;i++){
if(hh<=tt&&que[hh]<i-k+1) hh++;
while(a[que[tt]]>=a[i]&&tt>=hh) tt--;
que[++tt]=i;
if(i>=k-1)
cout<<a[que[hh]]<<" ";
}
cout<<endl;
hh=0,tt=-1;
for(int i=0;i<n;i++){
if(hh<=tt&&que[hh]<i-k+1) hh++;
while(hh<=tt&&a[que[tt]]<=a[i]) tt--;
que[++tt]=i;
if(i>=k-1)
cout<<a[que[hh]]<<" ";
}
cout<<endl;
//cout << "Hello world!" << endl;
return 0;
}