单调队列
作者:
呆呆小Y
,
2022-05-18 22:27:44
,
所有人可见
,
阅读 186
//单调队列!!!!!!!!!!
#include<bits/stdc++.h>
using namespace std;
int n,k,a[1000005],q[1000005];
int main()
{
int hh=0,tt=-1;
cin>>n>>k;
for(int i=0;i<n;i++)
cin>>a[i];
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)
cout<<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)
cout<<a[q[hh]]<<" ";
}
return 0;
}