单调队列 & 单调栈学习笔记

· · 算法·理论

单调队列

我们来讲单调队列。

单调队列顾名思义，就是单调递增/递减的队列。

单调队列主要解决的问题是：对于一个序列，用 O(n) 时间复杂度求出以 1 \sim n-k+1 为头，长度为 k 的区间最值，具体可以见 单调队列模板。

我们来讲如何求值。

刚刚说了，单调队列顾名思义，就是单调递增/递减的队列。

于是，每放进一个数，我们就拿其从后往前比较。为了更好讲，我们以求 \min 为例。

步骤如下：

样例如下：

8 3
1 3 -1 -3 5 3 6 7

单调队列变化过程见 OI-wiki。

具体应用有一定变化，我们来讲解一下。

1.单调队列优化 dp

个人不太喜欢，但还是讲一下。

以 P1725 为例题。

dp 比较好想，dp_i 就是在 [i-R,i-L] 中找一个 dp 值最大的，再加上 a_i 就好了。是单调队列板子，只是每次录入的不是 i，而是 i-L+1 罢了。

删除也要以 i-r 删除。

放个代码：

#include<bits/stdc++.h>
using namespace std;
const long long INF=-4e18;
long long a[200005],dp[200005];
int q[200005],h=1,t=1;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n,l,r;cin>>n>>l>>r;
    for(int i=0;i<=n;i++)cin>>a[i];
    dp[0]=0;q[1]=0;
    for(int i=1;i<=n;i++){
        while(h<=t&&q[h]<i-r)++h;
        if(i>=l&&h<=t)dp[i]=dp[q[h]]+a[i];
        else dp[i]=INF;
        int k=i-l+1;
        if(k>=0){
            while(h<=t&&dp[k]>=dp[q[t]])--t;
            q[++t]=k;
        }
    }
    long long ans=INF;
    for(int i=max(0,n-r+1);i<=n;i++)ans=max(ans,dp[i]);
    cout<<ans<<"\n";
    return 0;
}

2.单调队列求定长区间和最大或最小

乍一看这个标题可能比较奇怪，那么我们看这道例题：P1419，可能会清楚一点。

首先那个二分答案我们不说了，我们直接来说 check 的单调队列。

首先我们将每个数减去 mid。

然后，我们建立前缀和 s。

我们现在要求长度在 [S,T] 之间的一段，使其和大于 0。

转化。

我们来到第 i 个，前缀和为 s_i。

我们只要找出 [i-T,i-S] 中最小的前缀和就行了。

找出后与 s_i 比较大小，比 s_i 小返回 true。

然后没什么了，自己随便找点题练习吧，如果发现有别的类型可以联系我补。

单调栈

个人感觉单调栈用的比较少。

首先，我们要理解，单调栈和单调队列的区别其实就是栈和队列的区别。

看 P5788。

我们思考，对于 i \le j 如果 a_i \ge a_j，那么 j 对于任意 z 满足 1 \le z < i 失去了作用。但是，如果 a_i \le a_j，即使这个 z 可能用不上，但是对于之后的 z，a_j 还可能会发挥作用。

了解这一点，单调栈就很容易理解了。

步骤如下：

我们来讲点应用。

1.最大面积问题

以 P4147 为例。（其实 P1950 也是可以尝试一下的，但作者不想写就没做。）

这题不完全算是单调栈我觉得，但是也有一定的单调栈的思想去 dp。

我认为 这篇题解 还是很好的，如果一眼没秒掉建议阅读这篇题解。

具体思路其已经讲的很清楚了，不多赘述，不会的可以问我，能力范围内愿意回答。

2.不知道

我也不知道以什么为标题比较好，但扶苏的 B3666 真的是很好的一道单调栈模板，值得一做。

这其实难度不大，但真正诠释了单调栈的定义。首先，单调栈中的数一定递增，且在第 i 轮结束还存在于单调栈中的，一定是目前的后缀最大值。不知大家是否能理解，如果不行，这里再不要脸的引用一下扶苏姐姐的博客，说的很清楚。

然后没什么了，自己随便找点题练习吧，如果发现有别的类型可以联系我补。