栈是 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<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)\)。
观察代码核心部分：
// ……for(int i = 0; i < n; i++){ while(top && st[top] <= a[i]){ printf("pop %d.\n", st[top]); top--; } // ……}// ……注意里层的 while 循环，是用于弹出栈顶小于待插入元素的元素。
每个元素只入栈一次，也只会出栈一次，所以里层 while 循环总共只会执行 \(n\) 次，整个单调栈代码的时间复杂度为 \(O(n)\)。
Lougu P5788 【模板】单调栈
给定一个长度为 \(N\) 的数列，对于每个数，求出这个数之后第一个严格大于它的元素的下标。
发现正着做单调栈无法处理，考虑反着做。
此时就需要维护一个严格单调递减的栈，即插入元素前把栈顶小于它的元素全部弹出。
插入前如果栈为空，则答案为 \(0\)，否则为栈顶元素。
这题的一个要注意的点在于，要求的是元素的下标，所以栈要存储下标，而非数据。
题目使用的下标为 \(1 \sim 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;}POJ 3250 Bad Hair Day
Luogu P2866 [USACO06NOV]Bad Hair Day S
有 \(N (N \leq 80,000)\) 头奶牛排成一队，每只奶牛有一个身高 \(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 模板题。
Luogu P3865 【模板】ST 表
给定 \(n\) 个数和 \(m\) 组询问，每组询问有一个区间 \(l, r\)，求该区间最大值。
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<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;}维护一个栈，使得其存储的数据具有单调性，这样的栈叫做单调栈。
单调栈用于求解「序列中元素左/右第一个比它大/小的元素」。
因为每个元素最多各自进出栈一次，所以时间复杂度为 \(O(n)\)。
单调栈经常会搭配别的算法，常见的例如二分。
POJ 2559 Largest Rectangle in a Histogram
AcWing 131. 直方图中最大的矩形
给定 \(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