单调栈 (Monotonic Stack)

10 Aug 2025

1.简介

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

2.实现

对于长度为n的序列a，定义f(i)为第i个元素后第一个大于a[i]的元素的下标。若不存在，则f(i)为0。求f(1~n), \(数据范围:n \leq 3 \times 10^6\) 。


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]更大，则将栈顶元素pop. pop之后的新栈顶继续和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大，即栈顶比a[i]大，所以while不会执行。f(4)通过if语句赋值为5。将3加入栈中。
处理2。此时栈中含有3和5(栈顶为3)。3比2大，即栈顶比a[i]大，所以while不会执行。f(3)通过if语句赋值为3。将2加入栈中。
处理4。此时栈中含有2,3,5(栈顶为2)。4比2大，即a[i]比栈顶大，且栈不为空，所以执行while。while中，将2和3踢出栈。f(2)通过if语句赋值为5。将4加入栈中。
处理1。此时栈中还有4,5(栈顶为4)。4比1大，即栈顶比a[i]大，所以while不会执行。f(1)通过if语句赋值为4。

解析：

在从右向左的处理过程中，不断从栈中删去元素起到了优化的作用：当前元素若比栈顶元素大，则将栈顶元素删去。为什么可以把栈顶元素删去？在if语句中可知，我们始终把栈顶作为当前的答案，赋值给f[i]，并且不断更新栈顶。其逻辑是这样的：对于左边还未处理的元素，删去栈顶元素意味着这个栈顶元素不可能成为后面元素的答案。为什么呢？因为对于左边未处理的元素，我们已经找到了更加靠近的，且数字更大的元素，就是正在处理的元素。结合题目的要求，即找到所有元素右边第一个比它大的元素的下标，就很好理解了。

举个例子，入本题的样例。在处理元素4的时候，将2和3从栈中删除了。这样做是为了减少在求解后面元素的答案时所需要的时间。因为对于1而言，4要比2和3更加靠近1，并且数值更大，所以2和3肯定不可能是1的答案，所以将2和3删去。

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

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

最后，上文在解释时为了方便，都把入栈的操作说成是“一个元素入栈”。实际上是“元素的下标”入栈，因为题目求的是下标。而且在调用栈顶元素时，要记得要当做下标来用。如：

a[stk.back()]

3.变形

Example 1: 洛谷P2866

这题是一个简单的变形。所求的问题可简化为：找出每个元素左边第一个比它大的元素。对于所有的元素，以目标元素为左端点，当前元素为右端点，求区间长度之和。

Example 2: 洛谷U478856

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

此题难度比上题略高，不能简单的套用单调栈模版了。其核心思路是：对于每一个元素，找出以此元素为最大值的区间的数量。用c[i]表示以a[i]为最大值的区间数，那么答案则是： \(\sum_{i=1}^{n} c_i \times a_i\) 另外，求具体如何求区间数呢？需要从左到右，从右到左跑两遍单调栈，对于每一个元素，分别求左边第一个更大的元素，和右边第一个更大的元素。这样确定了最大的区间，但不是我们想要的。我们想要的是所有的区间数。

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

比如，在此数列中，对于元素7，在跑两遍单调栈后，我们得到对于7的最大区间，左端点为8，右端点为9 (不包括端点)。那么c[i] = (i - l) * (r - i)。其中，对于所有可能区间，i - l 表示了左端点的所有可能，r - i表示了右端点的算有可能。此公式可理解为一个排列问题。具体来看，对于7，c[7] = (5 - 2) * (7 - 5) = 6。

Example 3 洛谷B4273

此为一道单调栈的二维变形。如下图，每个长方形的底一样长，高不同，要找出一个面积最大的矩形，输入每个矩形的高。

此题和上题有异曲同工之妙。对于当前标红的纸条，向左右延伸，直到不能再延伸，以这种方式找到一个矩形，如图中用蓝框圈起的矩形。令此纸条高度为h，那么就找到了高度为h的矩形的面积的最大值。尝试所有的每个纸条的高度，求max，则能找到答案。

如何实现呢？已知输入代表了每个纸条的高度。对于每个数字，用单调栈，找到它左右第一个比它小的元素，求区间长度。用区间长度乘以纸条高度，就得到了当前高度的最大面积。


3 2 1 4 5 2

对于其他二维变形，可以把此题作为基础，将其他二维变形往这道题上去套，可能可以找到思路。

单调栈 (Monotonic Stack)

Related Posts