[编程笔记]-Monotonic_Queue单调队列

前言

update2024/08/07: 写的太乱了，刚好后面动规要引用，回来看了一眼不堪直视，遂重写

单调队列，在STL中有priority_queue（其实人家是堆hh），但事实上和单调队列还是有差距的，详见正文。

而滑动窗口，就是利用单调队列思想，实现的一种算法。

本博客会在单调栈的基础上讲解，所以不会的自助吧。

“[编程笔记]-Monotonic_Stack单调栈”

“[编程笔记]-Queue队列”

简介

具有单调性的队列。

具体的，事实上，它是一个双端队列，可以完成队头、队尾的插入删除操作。

如果你想维护单调性，肯定是需要维护队尾的不是么。

因此，单调队列和单调栈的唯一区别，就是需要从队头删除元素。

但是从队头删除元素就和单调性无关了。通常的，题目中都会有对于队列的限制，比如说限制队列长度之类的。为了维护这些性质，我们就需要从队头删除元素了（当然，如果题目没有要求，理论上来说你从队尾删除也没有任何问题，因此使用滑动窗口的题目中都会有要求的）。

模板

相对于一个数据结构单调栈来说，单调队列其实更有灵活性，并且表现得像一种思想或者说是算法。

当然你也可以用双端队列进行模拟，但介于那就是单调栈加上一些队头维护操作，那些操作还得根据题目要求来，就没有必要再给出模板了，直接找单调栈的即可。

所以就直接给例题吧。

滑动窗口

开个部分告诉你，会在例题中讲解滑动窗口问题。

例题

AcWing154-滑动窗口

值得注意的是：它用的也就是滑动窗口算法，只是说滑动窗口算法不只是这道题中的算法。

//手打双端队列模拟滑动窗口
#include<bits/stdc++.h>
using namespace std;

const int N=1e6+6;

int n,k;
int a[N];

int h1,t1,h2,t2;
int s1[N],s2[N];

int main(){
    cin>>n>>k;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    for(int i=1;i<=n;i++){
        if(h1<t1&&i-s1[h1+1]+1>k)h1++;
        while(h1<t1&&a[s1[t1]]>=a[i])t1--;
        s1[++t1]=i;
        if(i>=k)cout<<a[s1[h1+1]]<<" ";
    }
    cout<<"\n";
    for(int i=1;i<=n;i++){
        if(h2<t2&&i-s2[h2+1]+1>k)h2++;
        while(h2<t2&&a[s2[t2]]<=a[i])t2--;
        s2[++t2]=i;
        if(i>=k)cout<<a[s2[h2+1]]<<" ";
    }
    return 0;
}

完结撒花o(￣︶￣)o