单调队列入门

参考博客：https://www.luogu.org/blog/ybwowen/dan-diao-dui-lie

单调队列这个名字就指明了它的性质——单调性，是一个单调的双端队列

下面列出deque的常用成员函数：来自：https://blog.csdn.net/morewindows/article/details/6946811

 单调队列入门题目：P1886 滑动窗口 /【模板】单调队列

 

这里我们只讨论最大值，最小值原理一样的

很明显，当我们在计算区间[i−k+1,i]的最大值时，是不是区间[i−k+1,i−1]我们之前已经计算过了？那么我们是不是要保存上一次的结果呢（主要是最大值）？

这时，单调队列登场——单调队列主要有两个操作：删头和去尾

1.删头

如果队列头的元素离开了我们当前操作的区间，那么这

个元素就没有任何用了，我们就要把它删掉

2.去尾

假设即将进入队列的元素为X，队列尾指针为tail，这时我们要比较二者的大小：

1* X<q[tail] 此时q仍然保证着递减性，故直接将X插入队列尾

2*X>=q[tail] 此时，队列递减性被打破，此时我们做一下操作：

① 弹出队尾元素

因为当前的q[tail]不但不是最大值，对于以后的情况也不如X，所以要弹出

②重复执行①，直到满足X<q[tail]X<q[tail]或者队列为空为止

③将XX入队列

对于样例而言：

[1 3 -1] -3 5 3 6 7 
q={1},{3},{3,-1} output:3
1 [3 -1 -3] 5 3 6 7 
q={3,-1,-3} output:3
1 3 [-1 -3 5] 3 6 7
q={-1,-3},{-1,5},{5} output:5
1 3 -1 [-3 5 3] 6 7
q={5,3} output:5
1 3 -1 -3 [5 3 6] 7 
q={5,6},{6} output:6
1 3 -1 -3 5 [3 6 7]
q={6，7} output:7

由于每个元素最多入队一次，出队一次，所以时间复杂度为O(n)

当然，这题还可以用ST表和线段树来做，但都没有单调队列方便

实现：由于要对队首和队尾进行维护，所以我们需要使用双端队列

AC_Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e6+10;
const ll inf=0x3f3f3f3f3f3f3f3f;
#define dep(i,first,last) for(int i=first;i>=last;i--)
#define rep(i,first,last) for(int i=first;i<=last;i++)
#define lson l,mid,pt<<1
#define rson mid+1,r,pt<<1|1

template<typename T>void read(T &a){
    T x=0,f=1;
    char ch=getchar();
    while( !isdigit(ch) ){
        if( ch=='-') f=0;
        ch=getchar();
    }
    while( isdigit(ch) ){
        x=(x<<1)+(x<<3)+ch-'0';
        ch=getchar();
    }
    a=f?x:-x;
}

deque<int>q;
int a[maxn],n,m;
int main()
{
    read(n);
    read(m);
    rep(i,1,n) read(a[i]);
    rep(i,1,n){
        while(!q.empty() && a[q.back()]>a[i]) q.pop_back();
        q.push_back(i);
        if( i>=m ){
            while( q.front()<=i-m ) q.pop_front();
            printf("%d ",a[q.front()]);
        }
    }
    printf("
");
    while(!q.empty()) q.pop_front();
    rep(i,1,n){
        while(!q.empty() && a[q.back()]<a[i]) q.pop_back();
        q.push_back(i);
        if( i>=m ){
            while( q.front()<=i-m ) q.pop_front();
            printf("%d ",a[q.front()]);
        }
    }
    printf("
");
    return 0;
}