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

这是一道难度为 困难 的题目，它非常经典，结合了单调栈这一重要数据结构和对问题本质的洞察。我们会从最直观的思路开始，逐步优化，最终引出最高效的解法。

1. 题目描述

给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1。

求：在该柱状图中，能够勾勒出来的矩形的最大面积。

示例：
输入：heights = [2,1,5,6,2,3]
输出：10
解释：最大的矩形为图中阴影部分，面积为 10（柱子 5 和 6 组成的，高为5，宽为2）。

2. 核心问题分析

我们要找的是由柱子组成的最大矩形。这个矩形的高由什么决定？

• 矩形的高一定等于其中某根柱子的高度。因为矩形必须完整地包含这根柱子，所以它的高不能超过这根柱子的高。

因此，一个最直接的思路是：
依次考虑每一根柱子，将它作为矩形的高度，然后向左右两边扩展，直到遇到比它矮的柱子。这样我们就确定了以当前柱子为高的最大矩形的宽度。

矩形的面积 = 高 (当前柱子的高度) × 宽 (左右边界之间的距离)。

3. 解法一：暴力枚举（超时，但有助于理解）

我们可以为每一根柱子，分别向左和向右扫描，找到第一个比它矮的柱子位置。

• 对于柱子 i，高度为 h = heights[i]。
• 向左扫描：找到第一个满足 heights[left] < h 的索引 left。左边界为 left + 1。
• 向右扫描：找到第一个满足 heights[right] < h 的索引 right。右边界为 right - 1。
• 宽度：width = (right - 1) - (left + 1) + 1 = right - left - 1。
• 面积：area = h * width。

代码示例（Python风格伪代码）：

def largestRectangleArea(heights):
    n = len(heights)
    max_area = 0

    for i in range(n):
        h = heights[i]
        # 向左找左边界
        left = i
        while left - 1 >= 0 and heights[left - 1] >= h:
            left -= 1

        # 向右找右边界
        right = i
        while right + 1 < n and heights[right + 1] >= h:
            right += 1

        width = right - left + 1
        area = h * width
        max_area = max(max_area, area)

    return max_area

复杂度分析：

• 时间复杂度：O(n²)。对于每个柱子，最坏情况需要扫描整个数组。
• 空间复杂度：O(1)。

这种方法在数据量大时会超时，我们需要优化。

4. 解法二：优化思路与单调栈登场

暴力解法的瓶颈在于，对于每个柱子，我们都要重复地向左右扫描。我们能一次性知道每个柱子的左右边界吗？

可以，这就需要用到单调栈。

单调栈是一种特殊的栈，栈中的元素保持单调性（递增或递减）。在这里，我们使用单调递增栈。

核心思想：

• 我们遍历每个柱子。
• 如果当前柱子的高度大于等于栈顶柱子的高度，我们就将当前柱子的索引入栈。这保证了栈内柱子对应的高度是单调递增的。
• 如果当前柱子的高度小于栈顶柱子的高度，那么对于栈顶的柱子来说，它的右边界就是当前这个比它矮的柱子！而它的左边界，就是它在栈中的下一个元素（因为栈是递增的，下一个元素肯定比它矮）。

为什么？

• 因为栈是高度递增的，所以栈中某个元素的前一个元素，就是左边第一个比它矮的柱子。
• 当遇到一个比栈顶元素矮的柱子时，这个矮柱子就是栈顶元素的右边界（第一个比它矮的）。

具体步骤：

1. 在数组前后各加入一个高度为0的哨兵柱子，以处理边界情况。
   • 开头的0保证栈不会空，方便计算。
   • 结尾的0保证所有有效的柱子都能被弹出栈并计算面积。
2. 初始化一个空栈，用于存放柱子的索引。
3. 从左到右遍历每个柱子（包括哨兵）：
   • while 栈不为空 且 当前柱子的高度 < 栈顶柱子的高度：
     • 弹出栈顶元素，该元素的高度就是矩形的高 h。
     • 此时新的栈顶元素就是左边界（第一个比 h 矮的柱子）。
     • 当前遍历到的索引 i 就是右边界（第一个比 h 矮的柱子）。
     • 计算面积：h * (i - stack[-1] - 1)。
   • 将当前柱子的索引入栈。

5. 解法二详解：以示例推演

输入：heights = [2,1,5,6,2,3]
我们加入哨兵：[0, 2,1,5,6,2,3, 0]。索引从0开始。

初始化：stack = [0] (第一个哨兵的高度0的索引)
遍历开始 (i 从 1 到 7)：

• i=1, h=2:

  • 栈顶索引0对应高度0。2 > 0，直接入栈。
  • stack = [0, 1]

• i=2, h=1:

  • 栈顶索引1对应高度2。1 < 2，需要弹出计算。
    • 弹出索引1 (h=2)。此时栈顶为索引0 (h=0)。
    • 左边界是索引0，右边界是i=2。
    • 宽度 = 2 - 0 - 1 = 1。
    • 面积 = 2 * 1 = 2。
  • 现在栈顶是0 (h=0)，1 > 0，将i=2入栈。
  • stack = [0, 2]

• i=3, h=5:

  • 5 > 栈顶高度1，入栈。
  • stack = [0, 2, 3]

• i=4, h=6:

  • 6 > 5，入栈。
  • stack = [0, 2, 3, 4]

• i=5, h=2:

  • 2 < 栈顶高度6，弹出计算。
    • 弹出索引4 (h=6)。栈顶变索引3 (h=5)。
    • 宽度 = 5 - 3 - 1 = 1。
    • 面积 = 6 * 1 = 6。max_area=6
  • 2 < 栈顶高度5，继续弹出计算。
    • 弹出索引3 (h=5)。栈顶变索引2 (h=1)。
    • 宽度 = 5 - 2 - 1 = 2。
    • 面积 = 5 * 2 = 10。max_area=10
  • 现在栈顶高度1 <= 2，将i=5入栈。
  • stack = [0, 2, 5]

• i=6, h=3:

  • 3 > 2，入栈。
  • stack = [0, 2, 5, 6]

• i=7, h=0 (尾哨兵):

  • 0 < 栈顶高度3，弹出计算。
    • 弹出索引6 (h=3)。栈顶变索引5 (h=2)。
    • 宽度 = 7 - 5 - 1 = 1。
    • 面积 = 3 * 1 = 3。max_area=10
  • 0 < 2，继续弹出。
    • 弹出索引5 (h=2)。栈顶变索引2 (h=1)。
    • 宽度 = 7 - 2 - 1 = 4。
    • 面积 = 2 * 4 = 8。max_area=10
  • 0 < 1，继续弹出。
    • 弹出索引2 (h=1)。栈顶变索引0 (h=0)。
    • 宽度 = 7 - 0 - 1 = 6。
    • 面积 = 1 * 6 = 6。max_area=10
  • 最后将i=7入栈，循环结束。

最终最大面积为10。

6. 最终代码实现（Python）

def largestRectangleArea(heights):
    # 添加哨兵
    heights = [0] + heights + [0]
    stack = []
    max_area = 0

    for i in range(len(heights)):
        # 当当前高度小于栈顶高度时，开始弹出并计算
        while stack and heights[stack[-1]] > heights[i]:
            h = heights[stack.pop()]
            # 弹出后，左边界是新的栈顶元素
            left_index = stack[-1]
            width = i - left_index - 1
            area = h * width
            max_area = max(max_area, area)
        stack.append(i)
    return max_area

复杂度分析：

• 时间复杂度：O(n)。每个元素恰好入栈一次、出栈一次。
• 空间复杂度：O(n)。主要是栈的空间。

7. 总结与升华

• 关键洞察：最大矩形的高度必定是数组中某个柱子的高度。问题转化为对每个柱子，找其左右第一个比它矮的柱子（边界）。
• 暴力法：直观但效率低，用于理解问题。
• 单调栈优化：通过维护一个高度递增的栈，可以在一次遍历中高效地确定每个柱子的左右边界。哨兵技巧简化了边界处理。
• 思维提升：单调栈是解决“下一个更大/更小元素”类问题的利器，此题是其经典应用。

希望这个从暴力到优化的循序渐进讲解，能让你彻底理解「柱状图中最大的矩形」这道题！