单调栈是保持元素单调递增或递减的栈结构，用于解决下一更大/更小元素等问题。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 nextSmallerElement(const std::vector& arr) {
int n = arr.size();
std::vector result(n, -1); // 默认值为-1，表示右侧无更小元素
std::stack stk; // 存储的是索引
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 arr = {4, 2, 6, 1, 3};
std::vector res = nextSmallerElement(arr);
for (int val : res) {
std::cout }
// 输出: 2 1 1 -1 -1
return 0;
}
实现单调递增栈（找下一个更大元素）
只需调整比较方向即可实现单调递增栈，用于找每个元素右边第一个更大的元素。
std::vector nextGreaterElement(const std::vector& arr) {
int n = arr.size();
std::vector result(n, -1);
std::stack stk;
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)，因为每个元素最多入栈出栈一次
基本上就这些。掌握单调栈的核心在于理解其单调性维护机制，并灵活应用于各类“最近更大/更小元素”的场景。不复杂但容易忽略细节。
以上就是c++++中如何实现单调栈_c++单调栈实现方法的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/1477883.html
微信扫一扫 
支付宝扫一扫 
