【算法总结】单调栈和单调队列

蒟蒻中的zzh · 2023-07-02 09:22:26 · 个人记录

单调栈和单调队列知识总结

单调栈

单调栈是一种可以维护序列中向前或向后第一个比自己大或小的数据结构。

做法（以维护前面第一个比自己大的元素为例）：

贪心，我们从头往后扫描一遍数组，把每一个数加入栈中，在加入栈的时候，如果栈顶元素小于当前元素，就把栈顶元素弹掉，直到栈顶元素大于当前的元素。此时的栈顶元素即为所求。

正确性证明：

考虑对于三个数 a、b、c，假设他们的先后顺序是 a、b、c，且满足 a<b 和 b>c，则此时比 c 大的第一个数是 b，所以这时我们弹掉栈中的 a 是不会影响后面的结果的。如果满足 a<b 和 b<c，那么把 a 弹出更加不会影响 c 的结果了。

代码实现（定义与输入已省略）：

for(int i=1;i<=n;++i){
    while(top>0&&a[sta[top]]<a[i]) top--;
    ans[i]=sta[top];
    sta[++top]=i;
}

但是注意，如果当前的元素之前或之后没有比它大的元素的话，答案会被统计喂 sta_0，有时因为计算需要，需要我们把 sta_0 赋值为 n+1。

拓展：

其实仔细想想，我们可以发现，栈中的每一个数都是在碰到第一个比自己大的数的时候弹出的，所以说我们只用跑一遍单调栈就可以求出前后第一个比自己大的数了（但是我写代码的时候没想到，所以跑了两遍）。

复杂度分析：

不难看出，时间复杂度 O(n)，空间复杂度 O(n)。

经典例题：

P5788 【模板】单调栈

没什么好说的，核心代码已经在上面了。

P4147 玉蟾宫

我们可以预处理出每一个点往上走多远才会碰到第一个 R，设这个距离为 s_{i,j}，然后对于每一行，用单调栈处理出这个点向左和向右第一个 s_{i,j} 小于自己的点，从而算出以当前行为底、当前 s_{i,j} 为高且包括当前点的最大矩形的面积，最后对所有面积取 max 就行了。

核心代码：

for(int i=1;i<=n;++i){
    t=0;
    sta[0]=0;
    for(int j=1;j<=m;++j){
        while(t>0&&s[i][sta[t]]>=s[i][j]) t--;
        l[i][j]=sta[t];
        sta[++t]=j;
    }
    t=0;
    sta[0]=m+1;
    for(int j=m;j>=1;--j){
        while(t>0&&s[i][sta[t]]>=s[i][j]) t--;
        r[i][j]=sta[t];
        sta[++t]=j;
    }
    for(int j=1;j<=m;++j)
        ans=max(ans,s[i][j]*(r[i][j]-l[i][j]-1));
}

P1823 [COI2007] Patrik 音乐会的等待

对于两个人 a 和 b，他们能互相看到，当且仅当 b 是往后第一个比 a 高的人或者 a 是 b 前第一个比 b 高的人。很明显，这是一个单调栈。跑一遍单调栈，在把一个数弹出栈的时候统计答案（因为此时当前元素是往后第一个比栈顶元素大的数）。

但是值得注意的是，这一题身高相同的人也可以相互看到。那么对于一些串的与当前元素大小相等的栈顶元素，如果我们把他们弹出栈后只加入当前元素，后面我们弹出当前元素时，我们就会漏掉之前弹出的栈顶元素。所以我们要用一个数组来记录当前元素入栈时弹掉了多少个与自己相等的栈顶元素，最后统计答案的时候加上这个数组就行了。

核心代码：

for(int i=1;i<=n;++i){
    sum[i]=1;
    while(top>0&&a[sta[top]]<=a[i]){
        if(a[sta[top]]==a[i])
            sum[i]+=sum[sta[top]];
        ans+=sum[sta[top--]];
    }
    if(top!=0)
        ans++;
    sta[++top]=i;
}

单调队列

单调队列是一种可以维护动态区间最值的数据结构，但是不支持修改（这里的动态是指区间在动而不是数字有变动，而且只允许区间往一个方向动，长度可以改变）。

做法（以维护区间最大值为例）：

我们拓展区间的右端点，并把每一个数加入队列。对于每一个数，我们在加入之前先从队尾开始，把队尾小于自己的数都出队，然后将当前元素加入队尾，并记录位置。再从队头开始，把所有不在当前区间的数弹出。此时的队头即为所求。

正确性证明：

由于我们的区间只能向右移动，所以如果有这样两个元素 a、b 满足 a<b 且 a 比 b 更靠前，此时无论如何最大值都不可能是 a（因为 a 会比 b 先退出区间）。因此，我们就可以进行上述队尾出队的操作。对于两个数 a、b 满足 a>b 且 a 在 b 前面，我们不能把 b 出队，因为可能在区间左移的时候 a 被移出了区间，而最大值就有可能变为了 b，因此 b 得留在队列里头。所以，通过上述操作，我们就能维护出动态区间的最值。

代码实现：

for(int i=1;i<=n;++i){
    while(l<=r&&q1[r]<a[i]) r--;
    q1[++r]=a[i];
    q2[r]=i;
    while(l<=r&&q2[l]+k<=i) l++;// k 为区间长度
    ans[i]=q1[l];
}

但其实我们可以吧 q1 和 q2 合在一起，就像这样：

for(int int i=1;i<=n;++i){
    while(l<=r&&a[q[r]]<a[i]) r--;
    q[++r]=i;
    while(l<=r&&q[l]+k<=i) l++;
    ans[i]=a[q[l]];

复杂度：

时间：O(n)

空间：O(n)

基础例题：

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

没什么好说的，核心代码在上面了。

P3594 [POI2015] WIL

由于 1 \le w_i \le 10^9，我们一定要把变 0 的区间长度取到 d。那么我们用双指针，不断拓展区间的右端点，并维护当前区间中长度为 d 的区间的区间和最大是多少，当当前区间和减去长度为 d 的最大区间和还要大于 p 时，把区间的左端点向左移，直到上述值再次小于等于 p。上述值可以用单调队列和前缀和维护。

核心代码：

for(int i=d;i<=n;++i){
    while(l<=r&&s[i]-s[i-d]>s[q[r]]-s[q[r]-d]) r--;
    q[++r]=i;
    while(s[i]-s[t-1]-(s[q[l]]-s[q[l]-d])>p){
        t++;
        if(l<=r&&q[l]-d+1<t) l++;
    }
    ans=max(ans,i-t+1);
}

进阶用法：

矩阵最值

通过单调队列，我们可以求出一个矩阵中每个大小一定的子矩阵的最值。

做法：

设子矩阵大小为 m \times n，我们对每一列跑一遍单调队列，求出每列中每一个长度为 n 的区间的最值，存入一个数组中，再对于这个数组的每一行，求出长度为 m 的区间的最值，这个最值即为答案。

原理没什么好解释的，直接上代码（这里为 a \times b 的矩阵中求大小为 n \times n 的子矩阵的最值）：

for(int j=1;j<=b;++j){
    int la=1,ra=0,lb=1,rb=0;
    for(int i=1;i<=a;++i){
        while(la<=ra&&s[qa[ra]][j]<s[i][j]) ra--;
        while(lb<=rb&&s[qb[rb]][j]>s[i][j]) rb--;
        qa[++ra]=i;
        qb[++rb]=i;
        while(la<=ra&&i-qa[la]+1>n) la++;
        while(lb<=rb&&i-qb[lb]+1>n) lb++;
        maxx[i][j]=s[qa[la]][j];
        minx[i][j]=s[qb[lb]][j];
    }
}
for(int i=1;i<=a;++i){
    int la=1,ra=0,lb=1,rb=0;
    for(int j=1;j<=b;++j){
        while(la<=ra&&maxx[i][qa[ra]]<maxx[i][j]) ra--;
        while(lb<=rb&&minx[i][qb[rb]]>minx[i][j]) rb--;
        qa[++ra]=j;
        qb[++rb]=j;
        while(la<=ra&&j-qa[la]+1>n) la++;
        while(lb<=rb&&j-qb[lb]+1>n) lb++;
        maxn[i][j]=maxx[i][qa[la]];
        minn[i][j]=minx[i][qb[lb]];
    }
}

习题：P2216 [HAOI2007] 理想的正方形（核心代码就是上面的）

优化 dp

有些时候我们会发现，dp 转移时我们要找一个区间内的最值来进行转移，当这个区间只向一个方向移动时，我们就可以用单调队列维护这个最值，从而优化dp。

例题：P1725 琪露诺

从 i 点可以跳到 [i+L,i+R]，可以看成 i 可由 [i-R,i-L] 转移过来，于是用单调队列维护出 [i-R,i-L] 这个区间的 f_i 最值，再进行转移即可。

核心代码：

memset(f,128,sizeof(f));
f[0]=0;
for(int i=1;i<=n+R;++i){
    if(i-L>=0){
        while(l<=r&&f[q[r]]<f[i-L]) r--;
        q[++r]=i-L;
        while(l<=r&&q[l]<i-R) l++;
        f[i]=max(f[i],f[q[l]]+a[i]);
    }
}

总结

单调栈