单调栈是维护元素单调性的栈结构，能在 O(n) 时间内解决“找最近最值”问题。核心操作是根据当前元素弹出破坏单调性的栈顶元素。主要应用于寻找数组中某元素左侧或右侧最近的更大或更小元素下标。本文涵盖单调递增与递减栈的实现逻辑，结合洛谷 P5788、发射站及柱状图最大矩形等经典例题，讲解解题思路、代码模板及常见避坑点，适用于算法学习与面试准备。
提到栈，大家首先想到的是'先进后出'的线性结构，而，顾名思义，就是在普通栈的基础上，给元素加上了'单调性'的约束——栈内的元素必须（也可根据需求调整为非严格递增/递减）。
本质还是栈：完全遵循栈的'先进后出'规则，只是多了'维护单调性'的操作； 单调性可控：可维护单调递增栈（栈底到栈顶元素从小到大），也可维护单调递减栈（栈底到栈顶元素从大到小）； 操作高效：每个元素最多入栈一次、出栈一次，整体时间复杂度稳定在 O(n)。
话不多说，先看基础代码实现。我们以 C++ 为例，分别实现单调递增栈和单调递减栈：
#include <iostream>
#include <stack>
using namespace std;
const int N = 3e6 + 10; // 适配大数据量场景
int a[N], n; // 维护单调递增栈：栈内元素从小到大
void monotonicIncreasingStack() {
stack<int> st;
for (int i = 1; i <= n; i++) {
// 关键操作：弹出所有大于等于当前元素的栈顶元素，保证单调性
while (st.size() && st.top() >= a[i]) {
st.pop();
}
st.push(a[i]); // 插入当前元素，栈仍保持递增
}
}
// 维护单调递减栈：栈内元素从大到小
void monotonicDecreasingStack() {
stack<int> st;
for (int i = 1; i <= n; i++) {
// 关键操作：弹出所有小于等于当前元素的栈顶元素，保证单调性
while (st.size() && st.top() <= a[i]) {
st.pop();
}
st.push(a[i]); // 插入当前元素，栈仍保持递减
}
}
大家可能会疑惑：'为什么要先弹出元素再入栈？'其实这正是单调栈的核心——为了保证栈的单调性不被破坏。
比如维护单调递增栈时，若当前元素 a[i] 比栈顶元素小，说明栈顶元素'挡路'了：如果直接入栈，栈就会出现'大元素在前、小元素在后'的情况，违背递增规则。因此需要先弹出所有 ≥ a[i] 的元素，直到栈顶元素 < a[i]（或栈为空），再将 a[i] 入栈。
举个直观的例子：假设数组 a = [5, 3, 7, 2]，维护单调递增栈的过程：
i=1，a[i]=5：栈空，直接入栈 → 栈：[5] i=2，a[i]=3：栈顶 5≥3，弹出 5；栈空，入栈 3 → 栈：[3] i=3，a[i]=7：栈顶 3＜7，直接入栈 → 栈：[3,7] i=4，a[i]=2：栈顶 7≥2，弹出 7；栈顶 3≥2，弹出 3；栈空，入栈 2 → 栈：[2]
最终栈内元素为 [2]，完美保持递增特性。
单调栈的核心应用场景，总结起来就是'找最近最值'——给定一个元素，找到它左侧/右侧最近的、比它大/小的元素的位置。这四类问题看似不同，实则原理相通，掌握一种就能举一反三。
先记住一句'口诀'：找左侧，正遍历；找右侧，逆遍历；比它大，单调减；比它小，单调增。这句话能帮你快速确定遍历方向和栈的单调性，下文会反复验证。
给定数组 a，对于每个元素 a[i]，找到其左侧第一个比它大的元素的下标；若不存在，返回 0。
遍历方向：从左到右（找左侧元素，正序遍历）； 栈的单调性：维护单调递减栈（要找'更大'的元素，栈内元素从大到小，保证栈顶是最近的更大值）； 栈内存储：元素下标（最终要返回位置，存下标比存值更实用）。
#include <iostream>
#include <stack>
using namespace std;
const int N = 3e6 + 10;
int a[N], n;
int ret[N]; // 存储每个元素的答案
void findLeftLarger() {
stack<int> st; // 单调递减栈，存下标
for (int i = 1; i <= n; i++) {
// 弹出所有≤a[i]的元素，剩下的栈顶就是左侧最近的更大元素
while (st.size() && a[st.top()] <= a[i]) {
st.pop();
}
// 栈非空则栈顶是答案，否则为 0
if (st.size()) {
ret[i] = st.top();
} else {
ret[i] = 0;
}
st.push(i); // 入栈当前下标，维护栈的单调性
}
// 输出结果
for (int i = 1; i <= n; i++) {
cout << ret[i] << " ";
}
cout << endl;
}
int main() {
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
findLeftLarger();
return 0;
}
输入：
9 1 4 10 6 3 3 15 21 8
输出：
0 0 0 3 4 4 0 0 8
解释：
第 3 个元素 10，左侧最近的更大元素不存在 → 0； 第 4 个元素 6，左侧最近的更大元素是 10（下标 3） → 3； 第 9 个元素 8，左侧最近的更大元素是 21（下标 8） → 8。
给定数组 a，对于每个元素 a[i]，找到其左侧第一个比它小的元素的下标；若不存在，返回 0。
遍历方向：从左到右； 栈的单调性：维护单调递增栈（要找'更小'的元素，栈内元素从小到大，栈顶是最近的更小值）； 栈内存储：元素下标。
#include <iostream>
#include <stack>
using namespace std;
const int N = 3e6 + 10;
int a[N], n;
int ret[N];
void findLeftSmaller() {
stack<int> st; // 单调递增栈，存下标
for (int i = 1; i <= n; i++) {
// 弹出所有≥a[i]的元素，剩下的栈顶就是左侧最近的更小元素
while (st.size() && a[st.top()] >= a[i]) {
st.pop();
}
ret[i] = st.size() ? st.top() : 0;
st.push(i);
}
// 输出结果
for (int i = 1; i <= n; i++) {
cout << ret[i] << " ";
}
cout << endl;
}
int main() {
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
findLeftSmaller();
return 0;
}
输入：
9 1 4 10 6 3 3 15 21 8
输出：
0 1 2 2 1 1 6 7 6
解释：
第 4 个元素 6，左侧最近的更小元素是 4（下标 2） → 2； 第 5 个元素 3，左侧最近的更小元素是 1（下标 1） → 1； 第 9 个元素 8，左侧最近的更小元素是 15（下标 6） → 6。
给定数组 a，对于每个元素 a[i]，找到其右侧第一个比它大的元素的下标；若不存在，返回 0。
遍历方向：从右到左（找右侧元素，逆序遍历）； 栈的单调性：维护单调递减栈（找'更大'的元素，栈内递减）； 栈内存储：元素下标。
#include <iostream>
#include <stack>
using namespace std;
const int N = 3e6 + 10;
int a[N], n;
int ret[N];
void findRightLarger() {
stack<int> st; // 单调递减栈，存下标
for (int i = n; i >= 1; i--) {
// 弹出所有≤a[i]的元素，剩下的栈顶就是右侧最近的更大元素
while (st.size() && a[st.top()] <= a[i]) {
st.pop();
}
ret[i] = st.size() ? st.top() : 0;
st.push(i);
}
// 输出结果
for (int i = 1; i <= n; i++) {
cout << ret[i] << " ";
}
cout << endl;
}
int main() {
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
findRightLarger();
return 0;
}
输入：
9 1 4 10 6 3 3 15 21 8
输出：
2 3 7 7 7 7 8 0 0
解释：
第 1 个元素 1，右侧最近的更大元素是 4（下标 2） → 2； 第 7 个元素 15，右侧最近的更大元素是 21（下标 8） → 8； 第 8 个元素 21，右侧无更大元素 → 0。
给定数组 a，对于每个元素 a[i]，找到其右侧第一个比它小的元素的下标；若不存在，返回 0。
遍历方向：从右到左； 栈的单调性：维护单调递增栈（找'更小'的元素，栈内递增）； 栈内存储：元素下标。
#include <iostream>
#include <stack>
using namespace std;
const int N = 3e6 + 10;
int a[N], n;
int ret[N];
void findRightSmaller() {
stack<int> st; // 单调递增栈，存下标
for (int i = n; i >= 1; i--) {
// 弹出所有≥a[i]的元素，剩下的栈顶就是右侧最近的更小元素
while (st.size() && a[st.top()] >= a[i]) {
st.pop();
}
ret[i] = st.size() ? st.top() : 0;
st.push(i);
}
// 输出结果
for (int i = 1; i <= n; i++) {
cout << ret[i] << " ";
}
cout << endl;
}
int main() {
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
findRightSmaller();
return 0;
}
输入：
9 1 4 10 6 3 3 15 21 8
输出：
0 5 4 5 0 0 9 9 0
解释：
第 2 个元素 4，右侧最近的更小元素是 3（下标 5） → 5； 第 3 个元素 10，右侧最近的更小元素是 6（下标 4） → 4； 第 7 个元素 15，右侧最近的更小元素是 8（下标 9） → 9。
光说不练假把式，我们以洛谷经典模板题为例，完整拆解单调栈的解题流程。
给出项数为 n 的整数数列 a[1...n]，定义函数 f(i) 代表数列中第 i 个元素之后第一个大于 a[i] 的元素的下标，即 f(i)=min{ j | i<j ≤n, a[j]>a[i] }。若不存在，f(i)=0。试求出 f(1...n)。
n，第二行 n 个正整数 a[1...n]；n 个整数，表示 f(1),f(2),...,f(n)；这道题本质是'找右侧最近的更大元素'，直接套用前文的思路： 遍历方向：从右到左； 栈的单调性：单调递减栈； 栈内存储：元素下标。
#include <iostream>
#include <stack>
using namespace std;
const int N = 3e6 + 10; // 适配 3e6 的大数据量
int n;
int a[N];
int ret[N]; // 存储每个元素的答案
int main() {
ios::sync_with_stdio(false); // 关闭同步，加速输入输出
cin.tie(0); // 解绑 cin 和 cout
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
stack<int> st; // 单调递减栈，存下标
for (int i = n; i >= 1; i--) {
// 弹出所有≤a[i]的元素，保证栈的单调性
while (st.size() && a[st.top()] <= a[i]) {
st.pop();
}
// 栈顶即为右侧最近的更大元素下标
ret[i] = st.size() ? st.top() : 0;
st.push(i); // 入栈当前下标
}
// 输出结果
for (int i = 1; i <= n; i++) {
cout << ret[i] << " ";
}
cout << endl;
return 0;
}
输入：
5 1 4 2 3 5
输出：
2 5 4 5 0
解释：
a[1]=1，右侧最近的更大元素是a[2]=4→ f(1)=2；a[2]=4，右侧最近的更大元素是a[5]=5→ f(2)=5；a[3]=2，右侧最近的更大元素是a[4]=3→ f(3)=4；a[4]=3，右侧最近的更大元素是a[5]=5→ f(4)=5；a[5]=5，右侧无更大元素 → f(5)=0。
除了基础的'找最近最值'，单调栈还能解决很多经典算法题，下面选取两个高频考点，带你深入理解。
某地有 N 个能量发射站排成一行，每个发射站 i 有高度 H[i] 和能量值 V[i]，发射的能量只被两边最近的且比它高的发射站接收。求接收最多能量的发射站的能量值。
核心需求：对每个发射站，找到左侧/右侧最近的更高发射站，将能量值累加到对应发射站； 左侧更高：正序遍历，维护单调递减栈（找更高元素）； 右侧更高：逆序遍历，维护单调递减栈； 最终遍历所有发射站的能量总和，取最大值。
#include <iostream>
#include <stack>
using namespace std;
typedef long long LL; // 防止能量值溢出
const int N = 1e6 + 10;
int n;
LL h[N], v[N];
LL sum[N]; // 存储每个发射站接收的总能量
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> h[i] >> v[i];
}
// 第一步：找左侧最近的更高发射站
stack<int> st;
for (int i = 1; i <= n; i++) {
// 弹出所有≤当前高度的元素，栈顶即为左侧最近更高
while (st.size() && h[st.top()] <= h[i]) {
st.pop();
}
if (st.size()) {
sum[st.top()] += v[i]; // 能量累加到左侧更高的发射站
}
st.push(i);
}
// 第二步：找右侧最近的更高发射站（清空栈，重新遍历）
while (st.size()) st.pop();
for (int i = n; i >= 1; i--) {
while (st.size() && h[st.top()] <= h[i]) {
st.pop();
}
if (st.size()) {
sum[st.top()] += v[i]; // 能量累加到右侧更高的发射站
}
st.push(i);
}
// 第三步：找接收能量的最大值
LL ret = 0;
for (int i = 1; i <= n; i++) {
ret = max(ret, sum[i]);
}
cout << ret << endl;
return 0;
}
输入：
3 4 2 3 5 6 10
输出：7
解释：
发射站 1（H=4，V=2）：右侧最近更高是发射站 3，能量 2 传给 3； 发射站 2（H=3，V=5）：右侧最近更高是发射站 3，能量 5 传给 3； 发射站 3（H=6，V=10）：无更高发射站，无能量接收； 总接收：发射站 3 接收 2+5=7，为最大值。
给定 n 个宽度为 1 的矩形的高度，求包含于这些矩形的最大子矩形面积。
核心思路：对每个矩形
i，找到左侧/右侧最近的更矮矩形，确定该矩形能扩展的最大宽度，面积 = 高度 × 宽度； 左侧更矮：正序遍历，维护单调递增栈； 右侧更矮：逆序遍历，维护单调递增栈； 遍历所有矩形的面积，取最大值。
#include <iostream>
#include <stack>
using namespace std;
typedef long long LL; // 防止面积溢出
const int N = 1e5 + 10;
int n;
LL h[N];
LL left_bound[N], right_bound[N]; // 左侧/右侧最近更矮矩形的下标
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
while (cin >> n, n) { // 输入 0 结束
for (int i = 1; i <= n; i++) {
cin >> h[i];
}
// 第一步：找左侧最近的更矮矩形
stack<int> st;
for (int i = 1; i <= n; i++) {
while (st.size() && h[st.top()] >= h[i]) {
st.pop();
}
left_bound[i] = st.size() ? st.top() : 0;
st.push(i);
}
// 第二步：找右侧最近的更矮矩形
while (st.size()) st.pop();
for (int i = n; i >= 1; i--) {
while (st.size() && h[st.top()] >= h[i]) {
st.pop();
}
right_bound[i] = st.size() ? st.top() : n + 1;
st.push(i);
}
// 第三步：计算最大面积
LL ret = 0;
for (int i = 1; i <= n; i++) {
LL width = right_bound[i] - left_bound[i] - 1;
ret = max(ret, h[i] * width);
}
cout << ret << endl;
}
return 0;
}
输入：
7 2 1 4 5 1 3 3 4 1000 1000 1000 1000 0
输出：
8 4000
解释：
第一组数据：最大矩形是高度为 3、宽度为 2（下标 6-7），或高度为 4、宽度为 2（下标 3-4），面积 8； 第二组数据：4 个高度 1000 的矩形，宽度 4，面积 1000×4=4000。
单调性选择：找'更大'元素 → 维护单调递减栈；找'更小'元素 → 维护单调递增栈； 遍历方向：找左侧元素 → 正序遍历；找右侧元素 → 逆序遍历； 栈内存储：优先存下标（需返回位置时直接用，存值无法对应位置）； 时间复杂度：每个元素入栈/出栈各一次，O(n)，适配大数据量（如 3e6）。
数据范围：注意
int和long long的选择，避免溢出（如面积、能量值计算）； 输入输出优化：大数据量下需加ios::sync_with_stdio(false); cin.tie(0);，否则会超时； 栈的清空：多次使用栈时，需先清空（while(st.size()) st.pop();）； 边界处理：无对应元素时返回 0（或 n+1），需提前定义好边界值。
单调栈看似简单，实则是'贪心思想'与'栈结构'的完美结合。它的核心价值在于将嵌套循环的暴力解法，优化为线性时间复杂度，这也是算法优化的核心思路——用空间换时间，用数据结构约束逻辑。
掌握单调栈，不仅能解决'找最近最值'类问题，更能理解'如何通过维护数据结构的特性来简化问题'。建议大家结合本文的例题，手动模拟栈的入栈、出栈过程，真正吃透每一步操作的意义。相信通过反复练习，你也能熟练运用单调栈，轻松应对算法面试和竞赛中的相关问题！
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML转Markdown 互为补充。 在线工具，Markdown转HTML在线工具，online
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML转Markdown在线工具，online
通过删除不必要的空白来缩小和压缩JSON。 在线工具，JSON 压缩在线工具，online