请教LeetCode 84：柱状图中最大矩形的解法直觉

问题回顾 #

给定柱状图高度数组heights，找出可形成的最大矩形面积。比如输入[2,1,5,6,2,3]，输出是10，对应高度为5、6的两个柱子组成的矩形（高度5，宽度2）。

你尝试的决策树暴力解法本质是枚举所有可能的子数组，计算每个子数组的最小高度×宽度，时间复杂度达到O(2^n)，超时是必然的。而栈实现的最优解法时间复杂度是O(n)，下面拆解它的核心逻辑。

核心直觉：聚焦单个柱子的最大潜力 #

栈解法的核心思路是对每个柱子，计算以它的高度为矩形高度时，能扩展的最大宽度。这个矩形的面积就是「高度×最大宽度」，遍历所有柱子取最大值就是答案。

为什么要找左右两侧第一个比当前柱子矮的柱子？

• 假设当前柱子高度为h，左侧第一个比h矮的柱子索引是left，右侧第一个比h矮的柱子索引是right。
• 那么在left和right之间的所有柱子高度都≥h，意味着我们可以用h作为矩形的高度，宽度就是right - left - 1（因为left和right本身不算在有效范围内）。
• 这个宽度就是当前柱子能扩展的最大宽度，对应的面积就是该柱子能贡献的最大矩形面积。

栈解法的具体逻辑 #

栈里维护的是递增的柱子索引序列，这样我们可以在遍历过程中快速找到每个柱子的左右边界：

1. 遍历索引i从0到heights.size()（注意这里要多遍历一次，用虚拟的高度0触发剩余柱子的计算）
2. 当栈不为空，且当前高度（i等于数组长度时视为0）小于栈顶柱子的高度时：
   • 弹出栈顶索引top，该柱子的高度h = heights[top]
   • 计算宽度：如果栈为空，说明左侧没有比h矮的柱子，宽度就是i；否则宽度是i - 栈顶索引 - 1（栈顶此时就是左侧第一个比h矮的柱子）
   • 更新最大面积ans = max(ans, h * w)
3. 将当前索引i压入栈，保持栈的递增性

结合示例走一遍 #

以输入[2,1,5,6,2,3]为例：

• 当i=1（高度1），栈顶是0（高度2），1<2，弹出0：h=2，栈空，宽度=1，面积=2×1=2；压入1。
• 当i=4（高度2），栈顶是3（高度6），2<6，弹出3：h=6，栈顶是2（高度5），宽度=4-2-1=1，面积=6×1=6；
  继续比较，2<5，弹出2：h=5，栈顶是1（高度1），宽度=4-1-1=2，面积=5×2=10（这就是示例的最大面积）；
  此时栈顶1的高度1≤2，停止弹出，压入4。
• 最后i=6（虚拟高度0），触发弹出栈中剩余的1、4、5，依次计算它们的最大面积，最终最大面积还是10。

总结 #

栈解法通过维护递增栈，在遍历过程中动态确定每个柱子的左右边界，从而高效计算每个柱子的最大贡献面积，避免了暴力枚举的高时间复杂度。

内容的提问来源于stack exchange，提问作者Linda