单调栈是一种内部元素具有单调性的栈，可以解决与“以某个值为最值的最大区间”等问题。
例题：P2866 [USACO06NOV] Bad Hair Day S
有 \(N \ (1 \le N \le 80000)\) 头奶牛，第 \(i\) 头牛的身高为 \(h_i \ (1 \le h_i \le 10^9)\)。每只奶牛往右边看，可以看到严格小于它身高的牛的头顶，直到看到了身高不小于它的牛（看不到这头牛的头顶），或者右边没有其他奶牛为止。第 \(i\) 头牛可以看到的头顶数量为 \(C_i\)，求 \(\sum_{i=1}^n C_i\)。假设有 \(6\) 头牛，高度分别为 \(10,3,7,4,12,2\)，那么它们分别可以看到 \(3,0,1,0,1,0\) 头牛的头发，其总和为 \(5\)。
分析：如果使用暴力枚举求解，对于每一头牛都往右边枚举身高小于它的牛，那么时间复杂度是 \(O(n^2)\) 的，无法通过本题。
可以转变一下思路，求每头牛能看见几头牛，等价于计算每头牛能被多少其他牛看见。一头牛能被哪些牛看见？左边比它高的牛，再左边比它高的牛，……。可以维护一个序列，满足这个序列里存的都是对于第 \(i\) 头牛来说，其左边的身高比它高的牛的身高（这会是一个单调递减的序列），可以使用栈来进行维护。
最开始栈是空的。身高为 \(10\) 的牛进栈，原来栈里没有牛，那么答案增加 \(0\)；身高为 \(3\) 的牛来了，则需要从栈顶开始，把所有小于等于 \(3\) 的牛都出栈，此时左边剩 \(1\) 头牛，答案增加 \(1\)，然后再将其入栈；身高为 \(7\) 的牛来了，从栈顶开始，把所有小于等于 \(7\) 的牛都出栈（比如刚才入栈的 \(3\) 就要出栈），此时左边有 \(1\) 头牛，答案增加 \(1\)，然后再将其入栈，……，以此类推。
像这样维护一个值单调递减（或者递增）的数据结构，称为单调栈。
参考代码
#include <cstdio>
#include <stack>
using std::stack;
using ll = long long;
const int N = 80005;
int h[N];
int main()
{
int n; scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%d", &h[i]);
stack<int> s;
ll ans = 0; // 极端情况下，答案是n的平方级别，超过了int范围，需要long long类型
for (int i = 1; i <= n; i++) {
while (!s.empty() && s.top() <= h[i]) s.pop();
ans += s.size();
s.push(h[i]);
}
printf("%lld\n", ans);
return 0;
}
在本题中，单调栈能以 \(O(n)\) 的时间复杂度找到每一个元素右边第一个比它大的数字（就是把这个数字挤出栈的数字）。
例题：SP1805 HISTOGRA - Largest Rectangle in a Histogram
如果矩形的高度从左到右递增，那么答案是多少？显而易见，可以尝试以每个矩形的高度作为最终矩形的高度，并把宽度延伸到右边界，得到一个矩形，在所有这样的矩形面积中取最大值就是答案。
受这种思路启发，如果能够知道以每一个高度的矩形作为最终矩形的高度向左、向右最多能延伸到哪，则这一段之间的就是最终矩形的宽度，在所有这样的矩形面积中取最大的。而向左、向右最多能延伸到哪实际上就是找每个高度的左边、右边第一个高度低于自己的位置。这一点可以通过单调栈实现。
参考代码
#include <cstdio>
#include <stack>
#include <algorithm>
using std::max;
using std::stack;
using ll = long long;
const int N = 100005;
int h[N], l[N], r[N];
int main()
{
while (true) {
int n; scanf("%d", &n);
if (n == 0) break;
for (int i = 1; i <= n; i++) scanf("%d", &h[i]);
stack<int> s;
for (int i = 1; i <= n; i++) {
while (!s.empty() && h[s.top()] > h[i]) {
r[s.top()] = i; s.pop();
}
s.push(i);
}
while (!s.empty()) {
r[s.top()] = n + 1; s.pop();
}
for (int i = n; i >= 1; i--) {
while (!s.empty() && h[s.top()] > h[i]) {
l[s.top()] = i; s.pop();
}
s.push(i);
}
while (!s.empty()) {
l[s.top()] = 0; s.pop();
}
ll ans = 0;
for (int i = 1; i <= n; i++) {
ans = max(ans, 1ll * h[i] * (r[i] - l[i] - 1));
}
printf("%lld\n", ans);
}
return 0;
}
例题：P1950 长方形
小明今天突发奇想，想从一张用过的纸中剪出一个长方形。
为了简化问题，小明做出如下规定：
（1）这张纸的长宽分别为 \(n,m\)。小明将这张纸看成是由\(n \times m\)个格子组成，在剪的时候，只能沿着格子的边缘剪。
（2）这张纸有些地方小明以前在上面画过，剪出来的长方形不能含有以前画过的地方。
（3）剪出来的长方形的大小没有限制。
小明看着这张纸，想了好多种剪的方法，可是到底有几种呢？小明数不过来，你能帮帮他吗？输入格式
第一行两个正整数 \(n,m\)，表示这张纸的长度和宽度。
接下来有 \(n\) 行，每行 \(m\) 个字符，每个字符为*或者.。
字符*表示以前在这个格子上画过，字符.表示以前在这个格子上没画过。输出格式
仅一个整数，表示方案数。
样例输入
6 4 .... .*** .*.. .*** ...* .***样例输出
38数据规模
对 \(10\%\) 的数据，满足 \(1\leq n\leq 10,1\leq m\leq 10\)
对 \(30\%\) 的数据，满足 \(1\leq n\leq 50,1\leq m\leq 50\)
对 \(100\%\) 的数据，满足 \(1\leq n\leq 1000,1\leq m\leq 1000\)
分析：本题可以通过枚举矩形的四条边，然后判断里面是否全是没有画过的部分，但这样时间复杂度很高，所以需要优化效率。
以行为单位处理，统计以每一行为底边的句型数量。举个例子，假设目前在统计第 \(4\) 行。
令 \(h_i\) 表示第 \(i\) 列从底往上延伸空格子的数量，\(l_i\) 表示这一列左边第一个满足 \(h\) 值小于等于 \(h_i\) 的列号（如果没有的话就是 \(0\)），\(r_i\) 表示这一列右边第一个满足 \(h\) 值小于 \(h_i\) 的列号（如果没有的话就是 \(m+1\)）。
根据乘法原理，包括这一列最底下的小格子，同时又被这一列的高度限制的长方形的数量是 \((i - l_i) \times (r_i - i) \times h_i\)。为什么 \(l\) 和 \(r\) 的计算一个带等号另一个不带等号，因为这样计数才不会重复不会遗漏（思考为什么？）。每一行都用这种方式处理，然后将每一行的结果汇总就得到了整个问题的结果。
\(h_i\) 如何计算？如果这个格子是画过的格子，则 \(h_i = 0\)，否则 \(h_i\) 的值就是同一列上一行的 \(h_i\) 的值再加 \(1\)。
如何求得 \(l_i\) 和 \(r_i\) 呢？使用单调栈。求 \(r_i\) 需要找到严格小于的，那么判断是否将栈顶元素挤出时，如果待处理的元素等于栈顶元素时不必出栈，只有遇到更小的才会被挤出来，满足栈是单调不减的；而求 \(l_i\) 需要找到小于等于的，则从后往前计算，判断是否将栈顶元素挤出时，如果这个元素小于等于栈顶元素，那么栈顶元素就会被挤出，满足栈是单调递增的。
参考代码
#include <cstdio>
#include <stack>
using std::stack;
using ll = long long;
const int N = 1005;
char ch[N][N];
int h[N][N], l[N], r[N];
int main()
{
int n, m; scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) {
scanf("%s", ch[i] + 1);
for (int j = 1; j <= m; j++) {
h[i][j] = ch[i][j] == '*' ? 0 : h[i - 1][j] + 1;
}
}
ll ans = 0; // 需要考虑极端情况：n=m=1000，而且全是没画过的格子，长方形的数量是n的4次方数量级
for (int i = 1; i <= n; i++) {
// 为了方便在出栈时求出每个元素左边和右边的符合要求的位置
// 栈里实际存储的是下标而不是元素本身
stack<int> s;
// 顺着求右边第一个小于这个数的位置
for (int j = 1; j <= m; j++) {
while (!s.empty() && h[i][s.top()] > h[i][j]) {
r[s.top()] = j; s.pop();
}
s.push(j);
}
while (!s.empty()) {
r[s.top()] = m + 1; s.pop();
}
// 倒着求左边第一个小于等于这个数的位置
for (int j = m; j >= 1; j--) {
while (!s.empty() && h[i][s.top()] >= h[i][j]) {
l[s.top()] = j; s.pop();
}
s.push(j);
}
while (!s.empty()) {
l[s.top()] = 0; s.pop();
}
for (int j = 1; j <= m; j++) {
ans += 1ll * h[i][j] * (j - l[j]) * (r[j] - j);
}
}
printf("%lld\n", ans);
return 0;
}