单调栈

10 Aug 2025

1. 简介

单调栈 (Monotonic Stack) 是一种解题工具，而非算法。
单调栈在复杂题目中，不会单独出现，一般用于完成部分功能，如处理数据。
其模板问题是：对于数列中的某个元素，找出其左侧或右侧第一个比它大或小的元素的下标。

2. 实现

对于长度为 n 的序列 a，定义 f(i) 为第 i 个元素右侧第一个大于 a[i] 的元素的下标。若不存在，则 f(i) 为 0。求 f(1)、f(2)、…、f(n)。

数据范围：n ≤ 3 × 10⁶。


a[]: 1 4 2 3 5


f(): 2 5 4 5 0

样例解释：

i = 1 时，a[i] = 1。其右侧第一个比 a[1] 大的元素为 4，下标为 2，故 f(1) = 2。
i = 2 时，a[i] = 4。其右侧第一个比 a[2] 大的元素为 5，下标为 5，故 f(2) = 5。

思路：

用 vector 模拟单调栈，并用 f[] 数组记录答案。
从数列右侧向左处理。
对每个 a[i]，将其与栈顶元素比较。若 a[i] 更大，则弹出栈顶；继续比较新的栈顶，直到栈顶元素大于 a[i]，或栈为空。
若栈非空，栈顶元素就是 a[i] 的答案，即 f(i)。
最后将当前元素的下标压入栈中。

#include<bits/stdc++.h>
using namespace std;
int n;
int a[3000010];
int f[3000010];
vector<int> stk;
int main() {
	cin >> n;
	for(int i = 1; i <= n; i++)
		cin >> a[i];
	for(int i = n; i >= 1; i--) {
		while(!stk.empty() && a[stk.back()] <= a[i])
			stk.pop_back();
		if(!stk.empty())
			f[i] = stk.back();
		stk.push_back(i);
	}
	for(int i = 1; i <= n; i++)
		cout << f[i] << " ";
	return 0;
}

运行过程：

a[]:   1 4 2 3 5
index: 1 2 3 4 5

处理 5：此时栈为空，while 和 if 均不会执行，直接将 5 入栈。由于 5 的右侧没有元素，f(5) 为 0。
处理 3：此时栈中有 5，且 5 比 3 大，while 不会执行。if 语句将 f(4) 赋值为 5，再将 3 入栈。
处理 2：此时栈中有 3 和 5（栈顶为 3）。3 比 2 大，故 f(3) 被赋值为 3，再将 2 入栈。
处理 4：此时栈中有 2、3、5（栈顶为 2）。4 大于 2，执行 while，将 2 和 3 弹出。if 语句将 f(2) 赋值为 5，再将 4 入栈。
处理 1：此时栈中有 4 和 5（栈顶为 4）。4 比 1 大，故 f(1) 被赋值为 4。

原理：

从右向左处理时，不断从栈中删除元素正是优化的关键。若当前元素大于栈顶元素，就可以弹出栈顶。因为对左侧尚未处理的元素而言，当前元素既更靠近它们，数值也更大；被弹出的元素不可能再成为“右侧第一个更大元素”。

以本题样例为例：处理元素 4 时，2 和 3 会被从栈中删除。对于之后处理的元素 1，4 比 2 和 3 更靠近 1，且数值更大，因此 2 和 3 不可能成为 1 的答案。

另外，使用 vector 模拟单调栈，编码时更加方便，具体有以下优势：

可通过下标直接访问元素，如 vector[i]；而 stack 只能访问栈顶元素。
可以使用 STL 中的函数，如 sort、find。

最后，上文为了方便，将操作称为“元素入栈”。实际上入栈的是元素下标，因为题目要求输出下标。使用栈顶元素时，也要将其视为下标，例如：

a[stk.back()]

3. 变形

示例 1：洛谷 P2866

这是一道简单变形：找出每个元素左侧第一个比它大的元素。以该元素为右端点、左侧第一个更大元素为左边界，累加所有对应区间的长度。

示例 2：洛谷 U478856

题意：对于一个长度为n的序列，求出所有区间的最大值的和。

此题难度比上题略高，不能直接套用单调栈模板。核心思路是：对于每个元素，求以它为最大值的区间数量。设 c[i] 为以 a[i] 为最大值的区间数，则答案为 Σ_{i = 1}ⁿ c_i × a_i。

如何计算区间数量？从左到右、从右到左各运行一次单调栈，分别求每个元素左右两侧第一个更大的元素。这样可以确定该元素作为最大值时可扩展到的最大区间，进而计算所有合法区间的数量。

        4   8   3   5   7   1   9   6
            l           i       r
index   1   2   3   4   5   6   7   8

例如，数值 7 位于第 5 个位置。两次单调栈处理后，可得到其最大区间的左右开边界 l 和 r。于是 c[i] = (i - l) × (r - i)：i - l 是左端点的可能数量，r - i 是右端点的可能数量。具体到数值 7，c[5] = (5 - 2) × (7 - 5) = 6。

示例 3：洛谷 B4273

这是一道单调栈的二维变形。如下图，每个柱形的底宽相同、高度不同；给定各柱形高度，求面积最大的矩形。

此题与上题思路相通。对当前标红的柱形向左右延伸，直到无法继续延伸，便得到图中蓝框标出的矩形。若该柱形高度为 h，这就是高度为 h 的矩形所能取得的最大面积。枚举每个柱形高度并取最大值，即可得到答案。

实现时，对每个柱形使用单调栈，找出其左右两侧第一个比它矮的柱形，并据此得到可延伸区间的长度。区间长度乘以当前柱形高度，就是该高度对应的最大面积。


3 2 1 4 5 2

对于其他二维变形，也可以以此题为基础，尝试将问题转化为类似的形式。

单调栈

Related Posts