单调栈

栈

栈是 OI 中常用的一种线性数据结构。

栈的修改是按照后进先出的原则进行的，因此栈通常被称为是后进先出（last in first out）表，简称 LIFO 表。

下文均使用名为 st ，栈底为 st[1] ，栈顶为 st[top] 的数组模拟栈。

这样做的好处是，操作方便：

操作	代码
查询栈的大小	top
查询栈是否为空	top
查询栈顶元素	st[top]
插入元素 x$x$	st[++top] = x;
弹出栈顶元素	top--;

单调栈

何为单调栈

顾名思义，单调栈即满足单调性的栈结构。与单调队列相比，其只在一端进行进出。

严格？

严格不等式：只含有记号 >$>$ 或 <$<$ 的不等式称为严格不等式。

非严格不等式：含有记号 ≤$\le$ 或 ≥$\ge$ 的不等式称非严格不等式。

所以「严格大于」就是 >$>$，「严格小于」就是 <$<$。

严格单调递增（减），指的是除第一个元素外，每个元素都严格大于（小于）前一个元素。

应用

考虑这样一个问题：给定一个数列，对于每个数，求出这个数之前第一个严格大于它的数。

假设该数列为：[81,45,11,0,14,26]$[81,45,11,0,14,26]$，依次将元素插入栈。

如图 1-1，此时已插入前 4$4$ 个元素，下一个待插入元素为 14$14$。

图 1-1（图自 OI-Wiki）

为了找到 14$14$ 之前第一个比它大的元素，要维护单调性，将比 14$14$ 小的元素弹出，于是弹出 0$0$ 和 11$11$

如图 1-2，此时栈中 14$14$ 的前一个元素为 45$45$，所以 14$14$ 之前第一个大于它的元素是 45$45$。

图 1-2（图自 OI-Wiki）

假设下一个插入的元素为 x$x$。

如果 14≤x$14\le x$，那么那么 14$14$ 肯定不是（元素 x$x$ 的）答案，那么比 14$14$ 还小的 0,11$0,11$ 就更不可能是答案。

如果 14>x$14>x$，那么 14$14$ 就是答案，不用再考虑 0,11$0,11$。

所以，0,11$0,11$ 不会再对后面的答案产生贡献（影响），可以弹出。

借助单调性处理问题的思想在于及时排除不可能的选项，保持策略的高度有效性和秩序性，从而为我们作出决策提供更多的条件和可能的方法。

代码实现

#include<iostream>
#include<cstdio>

using namespace std;

int main(){
	
	int n = 6;
	int a[6] = {81, 45, 11, 0, 14, 26}, ans[6] = { };
	int st[6] = { }, top = 0;
	
	for(int i = 0; i < n; i++){
		while(top && st[top] <= a[i]){ // 注意要用 top 判栈是否为空，不为空才能判断
			printf("pop %d.\n", st[top]);
			top--;
		}
		
		if(top){
			ans[i] = st[top];
		}else{
			ans[i] = -1; // 前面没有比这个数大的，就输出 -1
		}
		
		printf("push %d.\n", a[i]);
		st[++top] = a[i];
		
		printf("stack: ");
		for(int j = 1; j <= top; j++){
			printf("%d ", st[j]);
		}
		puts("\n");
		
	}
	
	printf("ans: ");
	for(int i = 0; i < n; i++){
		printf("%d ", ans[i]);
	}
	
	return 0;
}

运行结果：

push 81.
stack: 81 

push 45.
stack: 81 45 

push 11.
stack: 81 45 11 

push 0.
stack: 81 45 11 0 

pop 0.
pop 11.
push 14.
stack: 81 45 14 

pop 14.
push 26.
stack: 81 45 26 

ans: -1 81 45 11 45 45 

时空复杂度

空间复杂度显然为 O(n)$O(n)$。

观察代码核心部分：

// ……
for(int i = 0; i < n; i++){
	while(top && st[top] <= a[i]){
		printf("pop %d.\n", st[top]);
		top--;
	}
	// ……
}
// ……

注意里层的 while 循环，是用于弹出栈顶小于待插入元素的元素。

每个元素只入栈一次，也只会出栈一次，所以里层 while 循环总共只会执行 n$n$ 次，整个单调栈代码的时间复杂度为 O(n)$O(n)$。

单调栈简单应用

单调栈模板题

题目链接

Lougu P5788 【模板】单调栈

题意概括

给定一个长度为 N$N$ 的数列，对于每个数，求出这个数之后第一个严格大于它的元素的下标。

分析

发现正着做单调栈无法处理，考虑反着做。

此时就需要维护一个严格单调递减的栈，即插入元素前把栈顶小于它的元素全部弹出。

插入前如果栈为空，则答案为 0$0$，否则为栈顶元素。

这题的一个要注意的点在于，要求的是元素的下标，所以栈要存储下标，而非数据。

题目使用的下标为 1∼n$1\sim n$，方便起见程序的下标也用 1∼n$1\sim n$。

参考代码

#include<iostream>
#include<cstdio>

using namespace std;

const int N = 3e6 + 10;

int n, a[N], ans[N];
int st[N], top;

int main(){
	
	scanf("%d", &n);
	
	for(int i = 1; i <= n; i++){
		scanf("%d", &a[i]);
	}
	
	for(int i = n; i > 0; i--){
		while(top && a[st[top]] <= a[i]){
			top--;
		}
		if(top){
			ans[i] = st[top];
		}else{
			ans[i] = 0;
		}
		st[++top] = i;
	}
	
	for(int i = 1; i <= n; i++){
		printf("%d ", ans[i]);
	}
	
	return 0;
}

Bad Hair Day

题目链接

POJ 3250 Bad Hair Day

Luogu P2866 [USACO06NOV]Bad Hair Day S

题意概括

有 N(N≤80,000)$N(N\le 80,000)$ 头奶牛排成一队，每只奶牛有一个身高 hi$h_i$，求每只奶牛可以看到前方多少只奶牛的头发的和。

分析

奶牛 A 看到了奶牛 B 的头发，就相当于奶牛 B 的头发被奶牛 A 看到了。

求每只奶牛可以看见后面多少个奶牛的头发比较困难，但可以求每只奶牛的头发可以被前面多少只奶牛看见，这两个求法最终的和是一样的。

于是问题就被转化为「每只奶牛的头发可以被前面多少只奶牛看见」。

使用单调栈，维护一个严格单调递减的栈。

参考代码

#include<iostream>
#include<cstdio>

using namespace std;

const int N = 8e4 + 10;

int n, x;
int st[N], top;
long long ans;

int main(){
	
	scanf("%d", &n);
	
	for(int i = 0; i < n; i++){
		scanf("%d", &x);
		while(top && st[top] <= x){
			top--;
		}
		ans += top;
		st[++top] = x;
	}
	
	printf("%lld\n", ans);
	
	return 0;
}

单调栈离线处理 RMQ 问题

「模板」ST 表

其实是 RMQ 模板题。

题目链接

Luogu P3865 【模板】ST 表

题意概括

给定 n$n$ 个数和 m$m$ 组询问，每组询问有一个区间 l,r$l,r$，求该区间最大值。

何为 RMQ

RMQ 是英文 Range Maximum(Minimum) Query 的缩写，意思是查询区间最大（最小）值。

常见算法：

算法	是否在线	预处理时间复杂度	单次询问时间复杂度	总时间复杂度	空间复杂度
ST 表	在线	O(nlogn)$O(n\log n)$	O(1)$O(1)$	O(nlogn+n)≈O(nlogn)$O(n\log n+n)\approx O(n\log n)$	O(nlogn)$O(n\log n)$
线段树	在线	O(n)$O(n)$	O(logn)$O(logn)$	O(n+mlogn)≈O(mlogn)$O(n+m\log n)\approx O(m\log n)$	O(n)$O(n)$
……	……	……	……	……	……
单调栈	离线	O(mlogm)$O(m\log m)$	O(logn)$O(\log n)$	O(mlogm+mlogn)≈O(mlogm)$O(m\log m+m\log n)\approx O(m\log m)$	O(n)$O(n)$

其中 n$n$ 为数组大小，m$m$ 为询问次数。

详细内容可以前往 RMQ - OI Wiki 查看。

在线与离线

如果某种算法可以即时回答每一个询问，则称该算法为在线的，否则称为离线的。

分析

读入所有询问，然后按询问的右端点从小到大排序。

依次处理元素，维护严格单调递减栈。

如果处理到某个询问的右端点，则二分单调栈，找出栈底开始第一个下标大于此次询问的 l$l$ 的元素，记录答案。

详见代码注释。

参考代码

#include<iostream>
#include<cstdio>
#include<algorithm>

using namespace std;

const int N = 1e5 + 10, M = 2e6 + 10;

struct qt{
	int id, l, r;
}q[M]; // 结构体存储询问

int n, a[N], m;
int st[N], top;
int ans[M];

bool cmp(qt x, qt y){
	return x.r < y.r;
} // 按右端点从小到大排序

int main(){
	
	scanf("%d%d", &n, &m);
	
	for(int i = 1; i <= n; i++){
		scanf("%d", &a[i]);
	}
	
	for(int i = 0; i < m; i++){
		q[i].id = i;
		scanf("%d%d", &q[i].l, &q[i].r);
	}
	
	sort(q, q+m, cmp);
	
	int nw = 0; // 当前处理的询问
	
	for(int i = 1; i <= n && nw < m; i++){ // 依次处理每一个元素，插入栈中，维护严格单调递减栈
		
		while(top && a[st[top]] <= a[i]){
			top--;
		}
		st[++top] = i;
		
		while(i == q[nw].r){ // 如果当前处理到某一个询问的右端点（因为右端点可能重复，所以用 while 而非 if）
			
			int l = 1, r = top; // 二分栈中第一个下标大于此次询问的 l 的元素
			while(l < r){
				int mid = (l + r) / 2;
				if(st[mid] >= q[nw].l){
					r = mid;
				}else{
					l = mid + 1;
				}
			}
			ans[q[nw].id] = a[st[l]]; // 记录答案
			
			nw++; // 处理下一个问题
		}
	}
	
	for(int i = 0; i < m; i++){
		printf("%d\n", ans[i]);
	}
	
	return 0;
}

总结

1. 维护一个栈，使得其存储的数据具有单调性，这样的栈叫做单调栈。

2. 单调栈用于求解「序列中元素左/右第一个比它大/小的元素」。

3. 因为每个元素最多各自进出栈一次，所以时间复杂度为 O(n)$O(n)$。

4. 单调栈经常会搭配别的算法，常见的例如二分。

练习

Largest Rectangle in a Histogram

题目链接

POJ 2559 Largest Rectangle in a Histogram

AcWing 131. 直方图中最大的矩形

题意概括

给定 n$n$ 个柱子的高，求出组成的多边形中最大的矩形的面积。

分析

观察发现，框出的最大矩形一定是以某个柱子为高的。

枚举每根柱子，找出左边第一个比它短的柱子，和右边第一个比它短的柱子，就可以算出以这个柱子为高的最大矩形的面积，最后所有答案取最大值即可。

「找出左边第一个比它短的柱子，和右边第一个比它短的柱子」用单调栈处理即可。

参考代码

#include<iostream>
#include<cstdio>

using namespace std;

const int N = 1e5 + 10;

int n;
int h[N], l[N], r[N];
int st[N], top;
long long ans;

int main(){
	
	while(scanf("%d", &n), n != 0){
		
		ans = 0;
		
		for(int i = 1; i <= n; i++){
			scanf("%d", &h[i]);
		}
		
//		处理左边第一个比它短的柱子 
		top = 0;
		for(int i = 1; i <= n; i++){
			while(top && h[st[top]] >= h[i]){
				top--;
			}
//			if(top){
//				l[i] = st[top];
//			}else{
//				l[i] = 0;
//			}
//			如果 top == 0，st[top] == st[0] == 0，所以也可以写成下面这个样子：
			l[i] = st[top];
			st[++top] = i;
		}
		
//		处理有边第一个比它短的柱子 
		top = 0;
		for(int i = n; i > 0; i--){
			while(top && h[st[top]] >= h[i]){
				top--;
			}
			if(top){
				r[i] = st[top];
			}else{
				r[i] = n+1;
			}
			st[++top] = i;
		}
		
		for(int i = 1; i <= n; i++){
			ans = max(ans, (long long)(r[i]-l[i]-1)*h[i]);
		} // 分别算出以每个柱子为高的矩形的最大面积 
		
		printf("%lld\n", ans);
		
	}
	
	return 0;
}

本文 PDF 下载

单调栈_完整版_陈举文.pdf

• 栈
• 单调栈
•     何为单调栈
•     严格？
•     应用
•     代码实现
•     时空复杂度
• 单调栈简单应用
•     单调栈模板题
•         题目链接
•         题意概括
•         分析
•         参考代码
•     Bad Hair Day
•         题目链接
•         题意概括
•         分析
•         参考代码
• 单调栈离线处理 RMQ 问题
•     「模板」ST 表
•         题目链接
•         题意概括
•         何为 RMQ
•         在线与离线
•         分析
•         参考代码
• 总结
• 练习
•     Largest Rectangle in a Histogram
•         题目链接
•         题意概括
•         分析
•         参考代码
• 本文 PDF 下载

__EOF__