单调队列
作用:在线性时间内找到滑动窗口中的最值。
注意 队列中应存下标
#include <iostream>
using namespace std;
const int N=1e6+10;
int a[N],q[N], hh=0, tt=-1;
int main()
{
int n,k;
cin>>n>>k;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=n;i++)
{
while(hh<=tt && i-k+1 > q[hh] ) hh++; //i-k+1 为滑动窗口的第一个元素的下标 若队首元素下标小于它 说明队列长度大于窗口了
while(hh<=tt && a[q[tt]]>=a[i]) tt--;
q[++tt]=i;
if(i-k+1>0) cout<<a[q[hh]]<<" ";
}
cout<<endl;
hh=0,tt=-1;
for(int i=1;i<=n;i++)
{
while(hh<=tt && i-k+1 > q[hh] ) hh++; //i-k+1 为滑动窗口的第一个元素的下标 若队首元素下标小于它 说明队列长度大于窗口了
while(hh<=tt && a[q[tt]]<=a[i]) tt--;
q[++tt]=i;
if(i-k+1>0) cout<<a[q[hh]]<<" ";
}
return 0;
}