好的，我们这次来详细讲解 LeetCode 第 84 题：柱状图中最大的矩形（Largest Rectangle in Histogram）。

1. 题目描述

给定一个非负整数数组 heights，表示柱状图中各个柱子的高度，每个柱子的宽度为 1。
求：在该柱状图中，能够勾勒出来的矩形的最大面积。

示例 1：
输入：heights = [2,1,5,6,2,3]
输出：10
解释：最大的矩形是高度为 5 和 6 的两个柱子组成的矩形（或高度 5 的柱子自身扩展成宽度 2），面积 = 5 × 2 = 10。
图示中最大矩形是柱 5 和柱 6 组成的矩形（实际是柱高 5 往右扩展到柱 6，高度取 5，宽度 2）。

示例 2：
输入：heights = [2,4]
输出：4

2. 理解题意

想象一排柱子，高度参差不齐。
我们要找一个矩形，这个矩形必须贴着x轴，并且完全被柱状图包含（即矩形的高度不能超过区间内最矮柱子的高度）。
矩形的面积 = 高度 × 宽度。
宽度 = 右边界索引 - 左边界索引 + 1（或者用右边界索引 - 左边界索引，取决于区间开闭定义）。

关键点：
对于某个柱子 i，如果我们要以它的高度 heights[i] 作为矩形的高度，那么矩形的宽度能有多大？

• 向左延伸，直到遇到比它矮的柱子（不能跨过去，否则高度不够）。
• 向右延伸，直到遇到比它矮的柱子。
• 宽度 = 右边界 - 左边界 - 1（具体看索引处理）。

3. 暴力解法（思路铺垫）

最直接的想法：

• 枚举所有可能的左右边界 (l, r)，矩形高度 = min(heights[l..r])，计算面积，取最大值。
• 时间复杂度 O(n²)，在 n 很大时（如 10^5）会超时。

优化一点的暴力：
对每个柱子 i，以它的高度为矩形高度：

1. 向左找第一个小于 heights[i] 的柱子索引 leftBound。
2. 向右找第一个小于 heights[i] 的柱子索引 rightBound。
3. 宽度 = rightBound - leftBound - 1。
4. 面积 = heights[i] * 宽度。
5. 取所有 i 的最大面积。

这个思路已经是 O(n²) 最坏情况（柱子高度递增时，向右要找到末尾）。

4. 单调栈思路引入

上面的瓶颈在于：对每个柱子，要 O(n) 时间找左右第一个比它小的位置。
我们可以用单调栈一次遍历就求出这些边界。

单调栈：栈内元素保持单调递增（或递减）。这里我们要求每个柱子左右第一个比它小的位置，适合用递增栈。

4.1 求左右边界

定义：

• left[i] = 第 i 根柱子左边第一个比它矮的柱子的索引（如果没有，设为 -1）。
• right[i] = 第 i 根柱子右边第一个比它矮的柱子的索引（如果没有，设为 n）。

那么以 heights[i] 为高的矩形宽度 = right[i] - left[i] - 1。

4.2 单调栈一次遍历求右边界

递增栈（栈内存索引）：
遍历 i：

• 当 heights[i] < 栈顶索引对应的柱子高度时，说明 i 是栈顶的“右边第一个更小”的位置，弹出栈顶，记录 right[栈顶] = i。
• 否则入栈。

遍历完后栈内剩余的元素，意味着右边没有比它们更小的，所以 right[...] = n。

同理，从左到右可求 left[i]（左边第一个更小的索引，没有设为 -1），也可以用一次遍历对称地做。

实际上，可以在一次遍历中同时确定左边界和右边界吗？
可以！仔细思考：当我们因为 heights[i] 比栈顶小而弹出栈顶时，此时的新栈顶就是弹出元素的左边第一个比它小的索引（因为栈递增，栈顶下面一个就是左边最近的小值）。
所以弹出时：

• 高度 = heights[stack.pop()]
• 右边界 = i
• 左边界 = 新栈顶（若栈空，左边界 = -1）
• 宽度 = i - new_stack_top - 1
• 面积 = 高度 × 宽度

这样一次遍历就可以计算所有可能的最大矩形。

5. 详细步骤演示例子

heights = [2,1,5,6,2,3]

初始化：
栈 stack = []
maxArea = 0

i=0：栈空，入栈0 → stack=[0]

i=1：h[1]=1，h[stack[-1]]=h[0]=2 > 1，所以要弹出栈顶0：

• 弹出0，高度=2，栈空，左边界=-1，右边界=1，宽度=1-(-1)-1=1，面积=2×1=2，maxArea=2
• 入栈1 → stack=[1]

i=2：h[2]=5，h[1]=1 < 5，直接入栈 → stack=[1,2]

i=3：h[3]=6，h[2]=5 < 6，入栈 → stack=[1,2,3]

i=4：h[4]=2，h[3]=6 > 2，弹出3：

• 高度=6，左边界=2（新栈顶），右边界=4，宽度=4-2-1=1，面积=6×1=6，maxArea=max(2,6)=6
• 栈=[1,2]
  现在 h[2]=5 > 2，继续弹出2：
• 高度=5，左边界=1（新栈顶），右边界=4，宽度=4-1-1=2，面积=5×2=10，maxArea=10
• 栈=[1]
  现在 h[1]=1 < 2，入栈4 → stack=[1,4]

i=5：h[5]=3，h[4]=2 < 3，入栈 → stack=[1,4,5]

遍历结束，栈内还有[1,4,5]，依次弹出：

弹出5：高度=3，左边界=4，右边界=6（n），宽度=6-4-1=1，面积=3，maxArea=10
弹出4：高度=2，左边界=1，右边界=6，宽度=6-1-1=4，面积=8，maxArea=10
弹出1：高度=1，左边界=-1，右边界=6，宽度=6-(-1)-1=6，面积=6，maxArea=10

最终 maxArea=10。

6. 算法总结

1. 初始化栈，maxArea=0。
2. 遍历 i 从 0 到 n：
   • 当栈不空且 heights[i] < heights[栈顶]：
     • 弹出栈顶 idx = pop()
     • 高度 h = heights[idx]
     • 左边界 = 栈空 ? -1 : 栈顶
     • 宽度 = i - 左边界 - 1
     • 面积 = h × 宽度
     • 更新 maxArea
   • i 入栈
3. 遍历结束后，若栈不空，同样方式弹出计算（右边界=n）。
4. 返回 maxArea。

时间复杂度 O(n)，空间复杂度 O(n)。

7. 代码实现（Python）

def largestRectangleArea(heights):
    stack = []
    max_area = 0
    n = len(heights)
    
    for i in range(n):
        while stack and heights[i] < heights[stack[-1]]:
            h = heights[stack.pop()]
            left = stack[-1] if stack else -1
            width = i - left - 1
            max_area = max(max_area, h * width)
        stack.append(i)
    
    while stack:
        h = heights[stack.pop()]
        left = stack[-1] if stack else -1
        width = n - left - 1
        max_area = max(max_area, h * width)
    
    return max_area

这样我们就从理解题意、暴力思路、单调栈优化，到详细步骤演示和代码，完整地讲解了 LeetCode 84 题。