单调队列与单调栈

前言

单调队列和单调栈有什么关系？两者都利用了某个性质维护了满足单调性的数据结构，及时排除不可能的决策，来方便快速处理一些问题。
单调队列和单调栈解决的是不同的问题，并不是一个问题的两种解法。

单调队列

算法

单调队列可以解决「滑动窗口」内的最值问题。
所谓「滑动窗口」，指的是一段移动的区间，并且区间的左端点和右端点都单调递增。
「滑动窗口」可以是固定长度，也可以不固定长度。

不妨假设我们要维护的是窗口的最大值，单调队列的核心思想在于如果一个数后来，还更大，那它就一定特别优秀，所以比之前它小的所有数可以全部扔掉（不可能成为答案），不影响答案。

通过一个伪代码来看一下这个数据结构（这个维护的是窗口内的最大值）：

插入：

while(单调队列有元素 && 单调队列队尾小于插入元素)弹出队尾;
插入要插入的元素到队尾;

也就是说，在插入一个元素时，我们弹出队尾所有比它劣的元素（因为它们出现早还比它劣，就直接扔掉）。这样之后，单调队列中，值满足单调递减，且下标满足单调递增。

取最大值：

while(单调队列队首元素在窗口外)弹出队首；
返回队首；

也就是说，取最大值时，有可能队首维护的元素已经跑出窗口了，我们就把它扔掉（这时候后面一定还有补上去的比它小一点点的元素）。

注意单调队列是一个双端队列，用 deque 维护。

模板

洛谷P1886 滑动窗口 /【模板】单调队列

看代码，再理解单调队列逻辑。

#include<bits/stdc++.h>
using namespace std;

int read(){
    int f=1,x=0;char c=getchar();
    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
    while(isdigit(c)){x=x*10+c-'0';c=getchar();}
    return x*f;
}


struct Node{
    int pos,val;
};
deque<Node> q1,q2;

const int N = 1e6+5;
int a[N];
int ans1[N],ans2[N];

void ins(int i){
    while(q1.size()&&q1.back().val>a[i])q1.pop_back();
    q1.push_back({i,a[i]});
    while(q2.size()&&q2.back().val<a[i])q2.pop_back();
    q2.push_back({i,a[i]});
}

int main(){
    int n=read(),k=read();
    for(int i=1;i<=n;i++)a[i]=read();

    // 先加入 [1,k)
    for(int i=1;i<k;i++)ins(i);
    
    for(int r=k;r<=n;r++){
        ins(r); // 插入新加入窗口的元素

        int l=r-k+1; // 左端点
        while(q1.front().pos<l)q1.pop_front(); // 删除所有在窗口之外的元素
        while(q2.front().pos<l)q2.pop_front();

        ans1[l]=q1.front().val;ans2[l]=q2.front().val;
    }

    for(int i=1;i<=n-k+1;i++)printf("%d ",ans1[i]);
    puts("");
    for(int i=1;i<=n-k+1;i++)printf("%d ",ans2[i]);

    return 0;
}

单调队列优化 dp

本质就是在 dp 的转移方程式中，需要转移的数值就是一个「滑动窗口」中的最值。这样就利用单调队列可以加速 dp。

多重背包问题

看一个例子：多重背包问题。
背包容量为 $W$，每个物品重量为 $w_i$，价值为 $v_i$，有 $k_i$ 个。
你应该学过两个做法：

1. 不做任何优化：复杂度 $O(W\sum k_i)$
2. 二进制分组：复杂度 $O(W\sum \log_2 k_i)$

我们考虑优化一下朴素的做法，写出转移方程：

$$f_{i,j}=\max_{k=0}^{k_i}(f_{i-1,j-k\cdot w_i}+v_i\cdot k)$$

令 $j=aw_i+b$，

$$f_{i,j}=\max_{k=0}^{k_i}(f_{i-1,(aw_i+b)-k\cdot w_i}+v_i\cdot k)\\ f_{i,j}=\max_{k=0}^{k_i}(f_{i-1,(a-k)w_i+b}-(a-k)v_i)+a\cdot v_i$$

所以说，$f_{i,j}$ 转移的状态就是前面 $k_i$ 个中 $f_{i-1,(a-k)w_i+b}-(a-k)v_i$ 最大的。

上面是在说什么呢？不妨假设物品的质量是 $3$。那么 $f_{i,4}$ 由 $f_{i,1}$ 转移而来，$f_{i,7}$ 由 $f_{i,4},f_{i,1}$ 转移而来，$\dots$
注意到余数相同的数的转移是“一脉相承”的，我们把余数相同的数称作「一组」。而在朴素算法中，我们没有用到这个性质，把所有可能的情况重复计算了。

因此，在计算一组中的 $f_{i,j}$ 时，我们只要找到前面 $k_i$ 个中最大的 $f_{i-1,aw_i+b}-a\cdot v_i$（注意是 $f_{i-1}$）。

计算每一个分组的每个状态的复杂度都是 $O(1)$ 的，总共有 $O(W)$ 个状态，因此总复杂度就是 $O(nW)$。

总结：完全背包的单调队列优化核心在于：按余数分组，然后组内的计算可以用单调队列。

洛谷P1776 宝物筛选

（用 deque 效率较低，建议换成手写的双端队列）

#include<bits/stdc++.h>
using namespace std;

int read(){
    int f=1,x=0;char c=getchar();
    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
    while(isdigit(c)){x=x*10+c-'0';c=getchar();}
    return x*f;
}

const int N = 4e4+5;
int dp[N];

struct Node{
    int pos,val;
};

int main(){
    int _=read(),W=read();
    int ans=0; // 重量为 0 的物品总价值（特判）
    for(int i=0;i<_;i++){
        int v=read(),w=read(),n=read();
        if(w==0){ // 特判
            ans += v*n;continue;
        }

        for(int j=0;j<w;j++){ // 余数是 j
            deque<Node> q;

            // 这 *一组* 转移的第 k 个
            for(int k=0;k*w+j<=W;k++){ 
                // 趁还没有更新，把上一次的状态插入单调队列 (dp[j+k*w]-k*v)
                while(q.size() && q.back().val<dp[j+k*w]-k*v)q.pop_back();
                q.push_back({k,dp[j+k*w]-k*v});

                // 窗口右移，这个状态拿了就会超过n个
                while(k-q.front().pos>n)q.pop_front(); 

                // 现在用单调队列最大值更新 dp[k*w+j] 的值
                dp[k*w+j]=max(dp[k*w+j], q.front().val+k*v);
            }
        }
    }

    printf("%d\n",dp[W]+ans);
    return 0;
}

单调栈

算法

我们之前说单调队列和单调栈解决的是不同的问题，那么单调栈解决的是什么问题呢？

单调栈解决的问题是「下一个比它大的元素」。（下一个/上一个，比它大/比它小等价）
形式化地：$i=1,2,\ldots,n$，求 $\displaystyle\min_{i<j\le n, a_j>a_i} j$。

这个问题可以用单调栈 $O(n)$ 解决。

解决方法：

• 从后往前处理；
• 对于每个元素，弹出栈顶小于等于它的元素；栈顶就是答案；（注意等于也要移除，因为我们要找的是严格比它大的元素）
• 将这个元素压入栈内。

为什么？若栈顶比当前元素小，那么它在当前元素后面，还比它小，那么非常劣，直接扔掉就好，不会影响答案。而这样处理之后栈顶就一定是第一个比它大的元素，就是答案。

注意若栈是空的，说明不存在这样的元素。

模板

洛谷P5788 【模板】单调栈

注意栈内保存的是元素的下标。

#include<bits/stdc++.h>
using namespace std;

int read(){
    int f=1,x=0;char c=getchar();
    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
    while(isdigit(c)){x=x*10+c-'0';c=getchar();}
    return x*f;
}

const int N = 3e6+5;
stack<int> s;
int a[N];
int ans[N];

int main(){
    int n=read();
    for(int i=1;i<=n;i++)a[i]=read();
    
    for(int i=n;i>0;i--){
        while(s.size() && a[s.top()]<=a[i])s.pop();
        ans[i]=s.size()?s.top():0;
        s.push(i);
    }

    for(int i=1;i<=n;i++)printf("%d ",ans[i]);
    return 0;
}