柱状图中最大的矩形
Largest Rectangle in Histogram
在柱状图中找出一块面积最大的矩形，矩形的高度由其中最矮的柱子决定。
在力扣中练习题目描述
给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
求在该柱状图中，能够勾勒出来的矩形的最大面积。
示例 1:
输入：heights = [2,1,5,6,2,3] 输出：10 解释：最大的矩形为图中红色区域，面积为 10
示例 2：
输入： heights = [2,4] 输出： 4
提示：
1 <= heights.length <=1050 <= heights[i] <= 104
解题思路
单调栈 · 一次扫描
栈里存高度递增的下标，遇到更矮的柱子就结算栈顶
固定一根柱子作为矩形的高度，它能向左右延伸多远，取决于两边第一个比它矮的柱子。对每根柱子都找左右边界，就是 O(n²)。
单调栈把“找左右第一个更矮”压成一次扫描：栈里保存高度递增的下标。遇到当前柱子比栈顶矮时，栈顶柱子的右边界就是当前下标 i；弹出后新的栈顶就是它的左边界。
末尾补一个高度 0 的哨兵，保证所有柱子最终都会弹出；栈内高度保持递增。
宽度是 i - left - 1，面积是 height * width。结算后把当前下标入栈，保持递增。
i=3 的柱高 4 入栈；栈内高度仍然递增。
- 1:2高2
- 3:4高4← top
末尾补一个高度 0 的哨兵，保证所有柱子最终都会弹出，不需要循环结束后再单独清栈。
自拟柱状图 [6,2,5,4,5,1,6] 在 i=5 时连续弹出 5、4、2，其中高度 4、宽度 3 的矩形面积 12 最大。
每根柱子最多入栈出栈一次，时间 O(n)，空间 O(n)。
易错点
- 忘记哨兵：最后栈里剩余的柱子没有结算。
- 宽度写成 i - left：多算了一格，应为 i - left - 1。
- 弹栈后没有更新 left：用的还是旧左边界。
- 比较用 > 而不是 >=：相等高度时可能少算宽度，但加上哨兵通常仍能得到正确答案；统一用 >= 更稳。
向两边扩展 · 枚举高度
以每根柱子为最矮柱，向左右扩展到第一个更矮的位置
思路最直观，但每个柱子都可能向两边扫完整个数组，最坏 O(n²)；仅作对照。
枚举每根柱子作为矩形的高度 h，向左走到第一个比 h 矮的柱子，向右走到第一个比 h 矮的柱子，中间全部可以纳入矩形。
面积是 h × (right - left + 1)，所有柱子取最大。正确性很直接，但每次扩展都可能扫过大量重复区间。
在随机数据上它通常比 O(n²) 的最坏情况快，但面试中如果要求线性，必须换成单调栈。
- 1枚举每根柱子作为高度。
- 2向左扩展到第一个更矮的柱子。
- 3向右扩展到第一个更矮的柱子。
- 4计算面积并更新最大值。
易错点
- 扩展条件用 > 而不是 >=：相等高度会把本可包含的柱子排除。
- 边界下标算错：宽度是 right-left+1。
代码与演示
主解法配有图解；对照解法用于比较思路、复杂度或实现方式。
heights = [6,2,5,4,5,1,6]末尾补一个高度 0 的哨兵，保证所有柱子最终都会弹出；栈内高度保持递增。
查看 C++ 代码
延伸阅读
- 单调栈适合解决“找左右第一个更大/更小元素”的一类问题，柱状图、接雨水、每日温度都用到它。
- 栈里存下标而不是高度，才能在弹出时计算宽度。