单调栈是保持元素单调递增或递减的栈结构，用于解决下一更大/更小元素等问题。1. 分为单调递增栈和单调递减栈，通过在入栈前弹出破坏顺序的元素维护单调性。2. 使用std::stack实现时通常存储数组下标，便于访问原数组和计算距离。3. 在寻找每个元素右侧第一个更小元素时采用单调递减栈，通过while循环持续弹出大于等于当前元素的栈顶元素。4. 寻找下一个更大元素则使用单调递增栈，调整比较条件为大于关系即可。5. 每个元素最多入栈出栈一次，时间复杂度为O(n)。核心在于理解单调性维护机制并应用于最近更大或更小元素问题。
单调栈是一种特殊的栈结构，其内部元素始终保持单调递增或单调递减的顺序。它常用于解决“下一个更大元素”、“最大矩形面积”等一类问题。在C++中，我们可以借助std::stack来高效实现单调栈。
什么是单调栈
单调栈分为两种：
- 单调递增栈：从栈底到栈顶元素值递增（允许相等为非严格递增）
- 单调递减栈：从栈底到栈顶元素值递减（允许相等为非严格递减）
维护单调性的关键是在入栈前，将破坏顺序的元素从栈顶弹出。
使用 std::stack 实现单调递减栈
下面以单调递减栈为例，实现在数组中找到每个元素右边第一个更小的元素（Next Smaller Element）。
立即学习“C++免费学习笔记（深入）”；
#include iostream>
#include
#include
std::vector
int n = arr.size();
std::vector
std::stack
for (int i = 0; i // 维护单调递减：当前元素小于栈顶对应值时，更新结果
while (!stk.empty() && arr[i] result[stk.top()] = arr[i];
stk.pop();
}
stk.push(i);
}
return result;
}
int main() {
std::vector
std::vector
for (int val : res) {
std::cout }
// 输出: 2 1 1 -1 -1
return 0;
}
实现单调递增栈（找下一个更大元素）
只需调整比较方向即可实现单调递增栈，用于找每个元素右边第一个更大的元素。
std::vectorint n = arr.size();
std::vector
std::stack
for (int i = 0; i // 当前元素大于栈顶元素时，更新结果
while (!stk.empty() && arr[i] > arr[stk.top()]) {
result[stk.top()] = arr[i];
stk.pop();
}
stk.push(i);
}
return result;
}
关键点总结
使用单调栈时需注意以下几点：
- 栈中通常存储数组下标而非元素值，便于访问原数组和计算距离
- 循环中通过 while 而不是 if 来持续弹出破坏单调性的元素
- 根据题目需求选择递增或递减栈
- 时间复杂度为 O(n)，因为每个元素最多入栈出栈一次
基本上就这些。掌握单调栈的核心在于理解其单调性维护机制，并灵活应用于各类“最近更大/更小元素”的场景。不复杂但容易忽略细节。
