C++怎么实现单调栈_C++解决直方图最大矩形【算法】

单调栈防越界核心是栈存索引且每次调用top前必判空；直方图最大矩形需在末尾补0以清空栈并计算所有情况；面积计算须用long long防溢出，宽度公式为i – left_bound – 1。

单调栈怎么写才不会越界

核心是栈里只存索引，不是存值；每次弹栈前必须检查栈是否为空。c++ 的 std::stack 不支持随机访问，也不能用 top() 之前不判空——这是最常崩的地方。

• 初始化栈时用 std::stack<int> stk;</int>，只压入下标（比如 i），别压 heights[i]
• 遍历到 i 时，只要 !stk.empty() && heights[i] 就持续弹栈
• 弹栈后立刻用 stk.empty() ? -1 : stk.top() 算左边界，避免访问空栈的 top()
• 右边界就是当前 i，左边界是弹完后栈顶（或 -1），宽度 = i - left - 1

直方图最大矩形为什么必须补0

不补哨兵会导致末尾一段递增序列永远没机会被计算。比如 [2,3,4,5] 全进栈后循环结束，但所有高度对应的矩形都没算。

• 在 heights 末尾 push 一个 0，强制清空栈并触发全部计算
• 不要在开头加 -1 或 0：左边界逻辑会变复杂，且 C++ 中负索引不合法
• 补 0 后数组长度 +1，遍历范围变成 [0, n)（n = heights.size()）
• 这个 0 只参与计算，不作为有效柱子，所以面积公式里高度取 heights[stk.top()] 没问题

用 vector 模拟栈比 stack 更稳吗

真没必要换。标准 std::stack 完全够用，反而用 vector 手动维护容易写错 pop_back() 和边界判断。

• std::stack 的 top()/pop()/empty() 语义清晰，编译器优化也成熟
• 有人想用 vector 是为了访问倒数第二个元素——但单调栈根本不需要，只依赖栈顶
• 若真要调试，临时改成 vector 并打印 v.back() 可以，但上线别留
• 性能上无差异：两者底层都是连续内存，stack 默认适配器就是 deque，但换成 vector 也没坏处

leetcode 84 题卡在 96/97 个用例怎么办

几乎全是整型溢出或下标越界。尤其注意宽度计算时的减法顺序和 int 类型范围。

立即学习“C++免费学习笔记（深入）”；

• 面积用 long long 存，别用 int：heights[i] 最大 1e4，宽度最大 1e5，乘积超 INT_MAX
• 左边界变量命名别叫 left，叫 left_bound，避免和循环变量 left 混淆
• 当 stk 弹空后，左边界是 -1，此时宽度 = i - (-1) - 1 == i，别手抖写成 i - 1
• 测试用例 [1] 和 [0] 必须过：补 0 后变成 [1,0] 或 [0,0]，逻辑要能扛住

边界条件比算法本身更花时间——栈空判断、补零位置、宽度公式里的 -1，三个地方错一个就挂。