题目描述
blablabla
样例
#include<iostream>
//单调队列
using namespace std;
const int N =1e+6 +10;
int n,k;
int a[N],q[N];
int main(){
cin.tie(0);
ios::sync_with_stdio(0);
cin>>n>>k;
for(int i=0;i<n;i++) cin>>a[i];
int hh=0,tt=-1;//hh对头在左边,tt队尾在右边
for(int i=0;i<n;i++){
if(hh<=tt && i-q[hh]+1 >k) hh++; //如果队列不为空&& i带q[hh]两指针距离大于k ,就要缩小,这里其实一般用while
//不用if。
while(hh<=tt && a[q[tt]] >= a[i] ) tt--;//如果队尾比要输入的a[i]的值大,删掉这个尾指针
q[++tt] = i; //把i地址给他
if(i+1 >=k) cout<<a[q[hh]]<<" ";//对头是最小的吧
}
cout<<endl;
hh=0,tt=-1;//hh对头在左边,tt队尾在右边
for(int i=0;i<n;i++){
if(hh<=tt && i-q[hh]+1 >k) hh++; //如果队列不为空&& i带q[hh]两指针距离大于k ,就要缩小,这里其实一般用while
//不用if。
while(hh<=tt && a[q[tt]] <=a[i] ) tt--;//如果队尾比要输入的a[i]的值(小 !!!!),删掉这个尾指针
q[++tt] = i; //把i地址给他
if(i+1 >=k) cout<<a[q[hh]]<<" ";//对头是最大的吧
}
}