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

模板及讲解

单调队列

单调队列是什么

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

单调队列的实现

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

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

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

代码

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#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

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