该用单调栈当需为每个位置快速找最近的满足大小关系的左右边界，如下一个更大/更小元素；其核心价值是将O(n²)暴力优化至O(n)，适用接雨水、柱状图最大矩形等题。
什么时候该用单调栈而不是双指针或遍历
单调栈的核心价值是解决「下一个更大/更小元素」类问题，尤其是当需要为每个位置快速找到最近的、满足大小关系的左侧或右侧边界时。暴力遍历时间复杂度是 O(n²)，而单调栈能压到 O(n)——前提是问题具有「后进先出 + 单调性依赖」特征，比如接雨水、柱状图最大矩形、每日温度、股票价格跨度等。
容易误用的场景：数组无序但不涉及“最近一个满足条件的邻居”，或者需要全局最值而非局部边界——这时用 std::max_element 或堆更合适。
关键判断点：如果你在循环中反复向左/右扫描找第一个大于当前值的位置，就该换单调栈了。
用 stack 还是 stack>？索引到底存不存
绝大多数情况下必须存索引，而不是原始值。因为最终要返回的是位置（如「下一个更大元素的下标」）或需要计算宽度（如矩形面积 = 高 × 宽，宽 = 右边界索引 − 左边界索引 − 1）。
立即学习“C++免费学习笔记（深入）”；
std::stack<int></int> 存索引是最轻量且安全的选择；只有当你需要同时携带额外元信息（如合并区间时的起始坐标、带权重的优先级）才考虑 std::stack<:pair int>></:pair>。
常见错误：
- 存值不存索引 → 无法处理重复元素（如
[2,2,2]），也拿不到位置信息 - 用
vector模拟栈（如pop_back()）但忘了清空或边界检查 → 越界访问 - 初始化栈时 push(-1) 表示“虚拟左边界”，但后续计算宽度时没减 1 → 宽度偏大
递增栈 vs 递减栈：怎么选，看问题是“找更大”还是“找更小”
口诀：栈内维持「目标方向的单调性」。想找「下一个更大元素」，就用单调**递减**栈（栈底→栈顶递减），这样栈顶永远是当前见过的最小候选，一旦遇到更大的数，它就是栈顶元素的“下一个更大”；反之，想找「下一个更小」，就用单调**递增**栈。
注意不是“栈本身升序/降序”，而是“从栈底到栈顶”的顺序。C++ 中 std::stack 只暴露 top()/pop()/push()，所以靠入栈逻辑维持单调性：
- 递减栈：while (!s.empty() && nums[i] > nums[s.top()]) { /* 处理 s.top() */ s.pop(); } s.push(i);
- 递增栈：while (!s.empty() && nums[i]
别记反——只要记住：每次新元素进来，它要“淘汰”所有挡在它前面、比它弱（对目标而言）的旧元素。
边界处理和清空栈的必要性
循环只扫一遍数组，但末尾可能还有未配对的元素留在栈里（比如最后几个数一直没遇到更大的）。这时候必须单独清空栈，否则会漏解。典型例子：接雨水中，栈中剩余索引对应的是“没有右边界”的柱子，它们的右边界是数组末尾；柱状图中，清空栈时以数组长度为右边界计算面积。
清空写法建议统一用：
while (!s.empty()) {
int idx = s.top(); s.pop();
int right = n; // 或 n - 1，依题意定
int left = s.empty() ? -1 : s.top();
// 计算逻辑...
}
容易被忽略的一点：如果题目要求返回「下一个更大元素的值」而非下标，记得用 nums[idx] 取值，别直接用 idx 当答案；而且初始结果数组要填 -1 表示不存在。
实际调试时，打印栈状态（如每步输出 s.size() 和 nums[s.top()]）比加断点更快定位卡点。
