AcWing 154. 滑动窗口
原题链接
简单
C++ 代码
//单调队列
#include <iostream>
using namespace std;
const int N=1000010;
int q[N],a[N];
int n,k;
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(hh<=tt && i-k+1>q[hh]) hh++;
while(hh<=tt && a[q[tt]]>=a[i]) tt--;
q[++tt]=i;
if(i>=k-1) printf("%d ",a[q[hh]]);
}
puts("");
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) printf("%d ",a[q[hh]]);
}
puts("");
}