柱状图最大矩形：用左右第一根更矮柱夹出宽度
以第 i 根为高，宽是「左起第一个更矮」到「右起第一个更矮」之间的格数。递增栈在弹出时这两个边界同时就绪。
栈里下标对应高度单调递增。遇到更矮的 height[i] 就弹出栈顶 h：右边界是 i，左边界是新栈顶，面积 h×(i−left−1)。栈底哨兵 −1，数组末尾哨兵 0 强制弹空。时间 O(n)，空间 O(n)。
这是 LeetCode 84. Largest Rectangle in Histogram。一组非负柱子 heights[i] 表示高，宽都是 1，求能框进柱状图里的最大矩形面积。矩形必须落地，不能悬空。
主例 heights = [2,1,5,6,2,3]。最大矩形用高 5、宽 2 罩住 [5,6]，面积 10。用最矮的 1 罩住全部 6 根只有 6，不是最大。演示在读到下标 4 的 2 时弹出 6 和 5，面积来到 10。
第一直觉是枚举左右边界再取中间最矮柱，O(n²) 能对。缺的是每个柱子作为「矩形的高」时，左右到底能伸多远。下面从这块缺口用单调栈一次求出所有边界。
弹出栈顶的那一刻，宽度刚好能算
任意最大矩形都可以改写成：高度等于矩形覆盖范围内最矮的那根柱子。于是枚举这根柱子 i，问题变成它左边第一个 < h[i] 的位置 L、右边第一个 < h[i] 的位置 R，面积 = h[i]×(R−L−1)。两边都没有更矮的，L=−1，R=n。
缺的是快速找「下一个更小」。对每个 i 再往左右扫是平方。单调递增栈的性质：栈里从底到顶高度不降；一旦来了更矮的 x，栈顶那些比 x 高的柱子，右边第一个更矮者就是当前 i。弹出后新的栈顶，是它左边第一个更矮者。两个边界同时出现，立刻结算。
从缺口写实现。栈先压哨兵 −1，表示左墙在数组外。遍历时把末尾想象成一根高度 0 的柱子，把还留在栈里的柱子全部弹出。循环里：当栈顶真实柱子高度大于当前 x，弹出，宽 = i − 新栈顶 − 1，挑战 area。然后把 i 入栈，保持递增。
用手走主例，数组看成 [2,1,5,6,2,3,0]。i=0 压入 2。i=1 读到 1，弹出 2，左墙 −1，宽 1，面积 2。压入 1。i=2、3 依次压入 5、6，栈里高度 1,5,6。i=4 读到 2：弹出 6，左边界是 5 的下标 2，宽 4−2−1=1，面积 6；再弹出 5，左边界是 1 的下标 1，宽 4−1−1=2，面积 10。演示第一帧就停在 i=4、area=10 这一刻。i=5 压入 3。i=6 哨兵 0 依次弹出 3、2、1，面积分别是 3、8、6，都打不过 10。演示第二帧栈被弹空，面积仍锁 10。
每个下标入栈出栈各一次，O(n)。不要在弹出条件里写成 ≥ 还是 > 时搞反：相等柱子可以互相延伸，应在更严格的「更矮」时才构成边界，代码用 > x 弹出。漏掉末尾哨兵，最后一根递增序列不会结算，主例末尾的 2、3 会算漏。
结算发生在出栈，不是入栈柱子入栈时右边界还不知道。只有被更矮的柱子（或末尾 0）逼出栈，右边才钉死。主例的 5 和 6 都是读到 2 才算面积。
Go：单调栈 + 哨兵
func largestRectangleArea(heights []int) int {h := append(heights, 0) // 末尾哨兵stack := []int{-1} // 左边界哨兵area := 0for i, x := range h {for len(stack) > 1 && h[stack[len(stack)-1]] > x {hi := h[stack[len(stack)-1]]stack = stack[:len(stack)-1]w := i - stack[len(stack)-1] - 1if hi*w > area { area = hi * w }}stack = append(stack, i)}return area}
1末尾补 0，把还在栈里的递增柱子全部逼出来。主例最后弹出 3、2、1。
2栈底 −1 让最左边的柱子也有左边界。宽公式是右−左−1。
3主例 i=4、x=2 时先结算高 6 宽 1，再结算高 5 宽 2，area 变成 10。
4len(stack)>1 保证不把 −1 当成柱子弹出。
总结
每根柱子找左右更矮边界，递增栈弹出时结算。主例 [5,6] 面积 10。
- 枚举左右端再取最矮是平方。改成枚举「作为高度的那根柱」。
- 弹出才知道右边界。入栈时不要算面积。
- 两端哨兵：−1 管左墙，末尾 0 管收尾。漏掉会少算。