什么是单调队列
一个双端队列,队列中元素单调增或者单调减
单调队列解决滑动窗口最值问题
首先求窗口中的最小值
设当前状态为
[[1 3 -1] -3 5 3 6 7]
要求当前窗口的最小值的话,有-1的加入的话,1和3就没有了存在的意义,从队列弹出。队列一定呈递增形式。此时队头顶为-1
到-3了同理,把-1弹出,队头为-3
为什么是单调增序列?
窗口如果划过了当前窗口最小值,应该出队头,由下一个可能的值担任最小值,这个值可能更新也可能不更新
操作方法
队列存储下标
当前进入的下标如果不满足单调性,从队尾弹出数据,直到满足单调性为止
窗口如果划过了队头元素,将队头弹出
所以,需要双端队列
//参考y总课上代码
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 10e6+10;
int a[N],q[N],hh,tt=-1;
//hh头,tt尾
//双端队列,存储当前数据的下标
//判断队列为空就是hh<=tt,而不是啥tt>-1了
int n,k;
int main()
{
cin>>n>>k;
for (int i = 0; i < n; i ++ )
{
scanf("%d", &a[i]);
}
for (int i = 0; i < n; i ++ )
{
while(hh<=tt&&a[i]<=a[q[tt]]) tt--;
if(hh<=tt&&i-k+1>q[hh]) hh++;
q[++tt]=i;
if(i-k+1>=0) cout<<a[q[hh]]<<' ';
}
cout<<endl;
hh=0,tt=-1;
for (int i = 0; i < n; i ++ )
{
while(hh<=tt&&a[i]>=a[q[tt]]) tt--;
if(hh<=tt&&i-k+1>q[hh]) hh++;
q[++tt]=i;
if(i-k+1>=0) cout<<a[q[hh]]<<' ';
}
cout<<endl;
return 0;
}