单调栈是解决“柱状图中最大矩形”最高效方法，时间复杂度o(n)，通过单栈一次遍历找到每个柱子左右首个更矮柱子位置，从而确定以该柱为高的最大矩形宽度与面积。
单调栈是解决“柱状图中最大矩形”（LeetCode 84）最经典且高效的解法，时间复杂度 O(n)，空间复杂度 O(n)，远优于暴力 O(n²)。核心在于：对每个柱子，快速定位它能向左、向右扩展的最远边界——即左右第一个比它矮的柱子位置，从而确定以该柱为高的最大矩形宽度。
关键逻辑：每个柱子的“有效宽度”由最近的更矮邻居决定
以高度 heights[i] 为矩形高时，矩形不能越过任何比它矮的柱子。因此：
- 左边界 = 左侧第一个 heights[j] 的索引 j（若无，则为 -1）
- 右边界 = 右侧第一个 heights[k] 的索引 k（若无，则为 n）
- 宽度 = k − j − 1
- 面积 = heights[i] × (k − j − 1)
单调栈的作用，就是用一次遍历，同时为所有 i 找到这两个边界。
单栈一次遍历写法（推荐，代码简洁）
只用一个单调递增栈（栈底→栈顶高度递增），在遍历中边入栈边结算。技巧是：在原数组末尾补一个 0，强制清空栈中所有剩余元素。
- 遍历下标 i 从 0 到 n（含虚拟末尾）
- 当前高度 h = (i == n) ? 0 : heights[i]
- 只要栈非空且 heights[stack.peek()] > h，就弹出栈顶 idx
- 弹出后，h_idx = heights[idx] 的右边界就是 i，左边界是栈新栈顶（若空则为 -1）
- 宽度 = i − (stack.isEmpty() ? -1 : stack.peek()) − 1
- 更新最大面积
双栈/双数组预处理写法（思路更直观）
先分别用单调栈算出 left[i] 和 right[i] 数组：
- left[i]：i 左侧第一个比 heights[i] 小的元素下标，初始全填 -1
- right[i]：i 右侧第一个比 heights[i] 小的元素下标，初始全填 n
- 正向遍历填 left：维护单调递增栈，遇到更小元素时，弹出并设其 right = 当前 i
- 反向遍历填 right：同理，维护单调递增栈（方向相反），弹出时设其 left = 当前 i
- 最后遍历 i，按 width = right[i] − left[i] − 1 计算面积
为什么单调栈能保证 O(n)？
每个下标最多入栈 1 次、出栈 1 次，总共 2n 次操作。看似嵌套 while 循环，但摊还分析下，内层循环总执行次数是线性的。本质是“延迟结算”+“即时释放”：栈里存的是还没找到右边界的所有候选，一旦遇到更小值，就立刻结算那些被挡住的柱子，不再回头重复查。
Java免费学习笔记：立即使用
解锁 Java 大师之旅：从入门到精通的终极指南
