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

发表于 | 分类于 | | + s

模板及讲解

单调队列

单调队列是什么

单调队列是一个双端队列两边都可以支持删除，并且队列里的数据都是单调的队列。单调队列可以方便查询距离当前位置左边一段连续区间最大最小值，常用于DP优化等单调性问题。类似滑动窗口。

单调队列的实现

以单调递增(维护最小值)的单调队列为例。

1、建立一个队列，都指向数组第一个位置。
2、加入数据$9,11,20$
3、之后加入$10$，序列为$(9,11,20,10)$ ，显然单调性被破坏
4、我们把比$10$大或者等于$10$的数都删除，最后得到的序列是$(9, 10)$，恢复了单调性，最左边元素即为最小值

这就是单调队列的一般步骤了，如果有长度限制，还要在处理前判断左边元素是否超出范围，超出则要删除。

代码

Bzoj 2442, 单调队列优化DP
注意队列数组开两倍，que[l]和l的区别

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
using namespace std;
const int MAXN = 100000 + 5;
int n, k;
LL tot, ei[MAXN], dp[MAXN], que[MAXN * 2];
void clean() {
    tot = 0;
    ms(dp, 0), ms(que, 0);
}
void solve() {
    clean();
    for (int i = 1; i <= n; i++) scanf("%lld", &ei[i]), tot += ei[i];
    int l = 1, r = 1;
    dp[0] = 0;
    for (int i = 1; i <= n; i++) {
        while (l <= r && que[l] < i - k - 1) l++;
        dp[i] = dp[que[l]] + ei[i];
        while (l <= r && dp[que[r]] >= dp[i]) r--;
        que[++r] = i;
    }
    LL mn = 1000000000000000000;
    for (int i = n - k; i <= n; i++) mn = min(mn, dp[i]);
    printf("%lld\n", tot - mn);
}
int main() {
    scanf("%d%d", &n, &k), solve();
    return 0;
}

单调栈

单调栈是什么

单调栈是一个栈内元素单调的栈。与单调队列相似，但是只有一边删除。

单调栈的实现

以从底到顶单调递增(维护最大值)的单调栈为例。

1、建立一个栈，都指向数组第一个位置。
2、加入数据$9,11,20$
3、之后加入$10$，序列为$(9,11,20,10)$ ，显然单调性被破坏
4、我们把比$10$大或者等于$10$的数都删除，最后得到的序列是$(9, 10)$，恢复了单调性，最上边元素即为最大值

代码

bzoj 1660

#include<cstdio>
#include<cstring>
#include<algorithm>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
using namespace std;

const int MAXN = 80000 + 5;

int n, hi[MAXN], top, stk[MAXN];

void clear() {
    top = 0;
}
void init() {
    clear();
    for (int i=1;i<=n;i++) scanf("%d", &hi[i]);
}
void solve() {
    LL ans = 0; 
    for (int i=1;i<=n;i++) {
        if (hi[i]<stk[top]) {
            ans += top;
        } else {
            while (top&&hi[i]>=stk[top]) top--;
            ans += top;
        }
        stk[++top] = hi[i];
    }
    printf("%lld\n", ans);
}
int main() {
    while (scanf("%d", &n)==1&&n) init(), solve();
    return 0;
}

常见题型

1、单调队列优化DP
Q：bzoj2442
解：bzoj2442
例题：bzoj 2442
2、单调栈维护i周围比i小的数
Q：bzoj1660
解：bzoj1660
例题：bzoj 1660

------ 本文结束 ------