栈
栈是 OI 中常用的一种线性数据结构。
栈的修改是按照后进先出的原则进行的，因此栈通常被称为是后进先出（last in first out）表，简称 LIFO 表。
下文均使用名为 st ，栈底为 st[1] ，栈顶为 st[top] 的数组模拟栈。
这样做的好处是，操作方便：
操作 代码 查询栈的大小 top
查询栈是否为空 top
查询栈顶元素 st[top]
插入元素
(x) st[++top] = x;
弹出栈顶元素 top--;
单调栈
何为单调栈
顾名思义，单调栈即满足单调性的栈结构。与单调队列相比，其只在一端进行进出。
严格？
严格不等式：只含有记号 (>) 或 (
非严格不等式：含有记号 (\leq) 或 (\geq) 的不等式称非严格不等式。
所以「严格大于」就是 (>)，「严格小于」就是 (
严格单调递增（减），指的是除第一个元素外，每个元素都严格大于（小于）前一个元素。
应用
考虑这样一个问题：给定一个数列，对于每个数，求出这个数之前第一个严格大于它的数。
假设该数列为：([81, 45, 11, 0, 14, 26])，依次将元素插入栈。
如图 1-1，此时已插入前 (4) 个元素，下一个待插入元素为 (14)。
图 1-1（图自 OI-Wiki）
为了找到 (14) 之前第一个比它大的元素， 要维护单调性，将比(14) 小的元素弹出，于是弹出(0) 和(11)
如图 1-2，此时栈中 (14) 的前一个元素为 (45)，所以 (14) 之前第一个大于它的元素是 (45)。
图 1-2（图自 OI-Wiki）
假设下一个插入的元素为(x) 。
如果(14 \leq x) ，那么那么(14) 肯定不是（元素(x) 的）答案，那么比(14) 还小的(0, 11) 就更不可能是答案。
如果(14 > x) ，那么(14) 就是答案，不用再考虑(0, 11) 。
所以，(0, 11) 不会再对后面的答案产生贡献（影响），可以弹出。
借助单调性处理问题的思想在于 及时排除不可能的选项，保持策略的高度有效性和秩序性，从而为我们作出决策提供更多的条件和可能的方法。
代码实现
#include
#include
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]
运行结果：
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))。
观察代码核心部分：
// ......
for(int i = 0; i < n; i++){
while(top && st[top]
注意里层的 while 循环，是用于弹出栈顶小于待插入元素的元素。
每个元素只入栈一次，也只会出栈一次，所以里层 while 循环总共只会执行(n) 次，整个单调栈代码的时间复杂度为(O(n)) 。
单调栈简单应用
单调栈模板题
题目链接
题意概括
给定一个长度为 (N) 的数列，对于每个数，求出这个数之后第一个严格大于它的元素 的下标。
分析
发现正着做单调栈无法处理，考虑反着做。
此时就需要维护一个 严格单调递减的栈，即插入元素前把栈顶小于它的元素全部弹出。
插入前如果栈为空，则答案为 (0)，否则为栈顶元素。
这题的一个要注意的点在于，要求的是元素的 下标，所以栈要存储下标，而非数据。
题目使用的下标为 (1 \sim n)，方便起见程序的下标也用 (1 \sim n)。
参考代码
#include
#include
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 0; i--){
while(top && a[st[top]]
Bad Hair Day
题目链接
Luogu P2866 [USACO06NOV]Bad Hair Day S
题意概括
有 (N (N \leq 80,000)) 头奶牛排成一队，每只奶牛有一个身高 (h_{i})，求每只奶牛可以看到前方多少只奶牛的头发的和。
分析
奶牛 A 看到了奶牛 B 的头发，就相当于奶牛 B 的头发被奶牛 A 看到了。
求每只奶牛可以看见后面多少个奶牛的头发比较困难，但可以求每只奶牛的头发可以被前面多少只奶牛看见，这两个求法最终的和是一样的。
于是问题就被转化为「每只奶牛的头发可以被前面多少只奶牛看见」。
使用单调栈，维护一个 严格单调递减的栈。
参考代码
#include
#include
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]
单调栈离线处理 RMQ 问题
「模板」ST 表
其实是 RMQ 模板题。
题目链接
题意概括
给定 (n) 个数和 (m) 组询问，每组询问有一个区间 (l, r)，求该区间最大值。
何为 RMQ
RMQ 是英文 Range Maximum(Minimum) Query 的缩写，意思是查询区间最大（最小）值。
常见算法：
算法 是否在线 预处理时间复杂度 单次询问时间复杂度 总时间复杂度 空间复杂度 ST 表 在线
(O(n \log n))(O(1))(O(n \log n + n) \approx O(n \log n))(O(n \log n))
线段树 在线
(O(n))(O(log n))(O(n + m \log n) \approx O(m \log n))(O(n))
…… …… …… …… …… …… 单调栈 离线
(O(m \log m))(O(\log n))(O(m \log m + m \log n) \approx O(m \log m))(O(n))
其中 (n) 为数组大小，(m) 为询问次数。
详细内容可以前往 RMQ – OI Wiki 查看。
在线与离线
如果某种算法可以即时回答每一个询问，则称该算法为 在线的，否则称为 离线的。
分析
读入所有询问，然后按询问的右端点从小到大排序。
依次处理元素，维护严格单调递减栈。
如果处理到某个询问的右端点，则二分单调栈，找出栈底开始第一个下标大于此次询问的 (l) 的元素，记录答案。
详见代码注释。
参考代码
#include
#include
#include
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 = 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;
}
总结
- 维护一个栈，使得其存储的数据具有单调性，这样的栈叫做单调栈。
- 单调栈用于求解「序列中元素左/右第一个比它大/小的元素」。
- 因为每个元素最多各自进出栈一次，所以时间复杂度为 (O(n))。
- 单调栈经常会搭配别的算法，常见的例如二分。
练习
Largest Rectangle in a Histogram
题目链接
POJ 2559 Largest Rectangle in a Histogram
题意概括
给定 (n) 个柱子的高，求出组成的多边形中最大的矩形的面积。
分析
观察发现， 框出的最大矩形一定是以某个柱子为高的。
枚举每根柱子，找出左边第一个比它短的柱子，和右边第一个比它短的柱子，就可以算出以这个柱子为高的最大矩形的面积，最后所有答案取最大值即可。
「找出左边第一个比它短的柱子，和右边第一个比它短的柱子」用单调栈处理即可。
参考代码
#include
#include
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 = 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
本文 PDF 下载
Original: https://www.cnblogs.com/cjwen6/p/15890215.html
Author: cjwen6
Title: 单调栈
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/711449/
转载文章受原作者版权保护。转载请注明原作者出处！