什么是单调队列？

百度百科

单调队列，即单调递减或单调递增的队列。

单调队列能干什么？

实现快速寻找区间的最大值与最小值

如何实现单调队列？(这里使用了STL的deque)

①建立结构体

因为我们之后要判断队首的元素是不是已经超出了滚动窗口，所以得把每个值记录他原来的位置

struct node{    int num,id;};

②判断原来的队首是不是还在滚动窗口内(并且输出当前的队首)

if(q.front().id+m

③对新进的数进行插入

(1)按照条件删除队尾的数，如果是单调增的单调序列那么删掉队尾大于等于当前值的值，这样求的就是滚动窗口内的最小值

(2)插入当前数据

while(!q.empty()&&q.back().num>=a[i])    q.pop_back();    q.push_back((node){a[i],i});

完整代码(洛谷 P1440 求m区间内的最小值)

#include 
    
     using namespace std;struct node{    int num,id;};deque
     
       q;int a[2000005];int main(){    ios::sync_with_stdio(0);    cin.tie(0);    cout.tie(0);    int n,m;    cin>>n>>m;    for(int i=1;i<=n;i++)    cin>>a[i];    for(int i=1;i<=n;i++)    {        if(q.empty())        cout<<"0\n";        else        {            if(q.front().id+m
      
       =a[i])        q.pop_back();        q.push_back((node){a[i],i});    }}
      
     
    

说明

这个模板仅仅适用于洛谷P1440对于其他的题来说并不适用

①这个把还没有攒到指定区间的前几个数的也都输出了

②这个没有输出最后一个区间

解决方法

①的解决方法仅需在输出范围队首的时候的前面加一个判断条件

if(i>=1+k)

②的解决方法只需要把i<=n改成i<=n+1保险的做法是下面把while条件也加一个i<=n

更改后的代码(洛谷 P1886 滑动窗口)

#include 
    
     using namespace std;struct node{  int num,id;};int a[1000005];deque
     
       q1,q2;int main(){  ios::sync_with_stdio(0);  cin.tie(0);  cout.tie(0);  int n,k;  cin>>n>>k;  for(int i=1;i<=n;i++)  cin>>a[i];  for(int i=1;i<=n+1;i++)  {    if(!q1.empty())    {      if(q1.front().id+k
      
       =1+k)      cout<
       
        <<" ";    }    while(!q1.empty()&&q1.back().num>=a[i]&&i<=n)    q1.pop_back();    q1.push_back((node){a[i],i});  }  cout<<"\n";  for(int i=1;i<=n+1;i++)  {    if(!q2.empty())    {      if(q2.front().id+k
        
         =1+k)      cout<
         
          <<" "; } while(!q2.empty()&&q2.back().num<=a[i]&&i<=n) q2.pop_back(); q2.push_back((node){a[i],i}); }}