好的，我们接下来讲解 LeetCode 第 85 题：最大矩形（Maximal Rectangle）。

1. 题目描述

给定一个仅包含 '0' 和 '1' 的二维二进制矩阵，找出只包含 '1' 的最大矩形，并返回其面积。

示例 1：
输入：

matrix = [
  ["1","0","1","0","0"],
  ["1","0","1","1","1"],
  ["1","1","1","1","1"],
  ["1","0","0","1","0"]
]

输出：6
解释：最大矩形如图所示（右下角 3×2 矩形）。

示例 2：
输入：matrix = [["0"]]
输出：0

示例 3：
输入：matrix = [["1"]]
输出：1

2. 问题分析

这个问题是二维的，直接枚举所有矩形会非常耗时（O(m²n²)）。
我们需要一个高效的方法。

一个经典思路是：
将二维问题转化为多个一维问题，利用我们已经熟悉的一维问题的解法。

3. 思路转化

3.1 一维问题回顾

先回顾一下 LeetCode 第 84 题「柱状图中最大的矩形」：
给定一个非负整数数组 heights，表示柱状图每个柱子的高度，求最大矩形面积。
我们使用单调栈可以在 O(n) 时间内解决。

3.2 如何将本题转化为第 84 题？

对于矩阵的每一行，我们可以计算以该行为底边，每一列向上连续 '1' 的个数（高度）。
例如对于示例 1：

• 第 0 行：[1,0,1,0,0] → 高度 [1,0,1,0,0]
• 第 1 行：[1,0,1,1,1] → 高度 [2,0,2,1,1]（遇到 0 则高度归零，否则累加）
• 第 2 行：[1,1,1,1,1] → 高度 [3,1,3,2,2]
• 第 3 行：[1,0,0,1,0] → 高度 [4,0,0,3,0]

这样，每一行的高度数组就是一个柱状图，我们可以用第 84 题的解法求出该行对应的最大矩形面积。

4. 算法步骤

1. 初始化一个数组 heights，长度等于矩阵列数 n，初始为全 0。
2. 遍历每一行 i：
   • 更新 heights[j]：如果 matrix[i][j] == '1'，则 heights[j] += 1，否则 heights[j] = 0。
   • 对当前行的 heights 数组，用单调栈法计算最大矩形面积（第 84 题解法）。
3. 记录所有行中最大的面积。

5. 单调栈解法回顾（第 84 题）

对于数组 heights，我们想快速找到每个柱子左右第一个比它矮的柱子的位置，从而确定以该柱子为高的矩形的宽度。

• 用单调递增栈存储下标。
• 遍历每个高度：
  • 当栈不为空且当前高度 < 栈顶高度时，说明找到了栈顶柱子的右边界。
  • 弹出栈顶，计算以该柱子高度为高的矩形面积：
    高度 = heights[栈顶]
右边界 = 当前索引 i
左边界 = 新栈顶索引（若栈空则为 -1）
宽度 = i - 左边界 - 1
面积 = 高度 × 宽度
• 遍历结束后，栈中剩余的柱子右边界为数组长度 n，同样方式计算面积。

6. 逐步演算示例 1

矩阵：

1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0

第 0 行高度： [1,0,1,0,0]
单调栈过程：

• i=0, h=1，栈空，入栈 [0]
• i=1, h=0 < h[0]=1 → 弹出 0：左边界 -1，右边界 1，宽度=1-(-1)-1=1，面积=1×1=1
• i=1, 栈空，入栈 [1]
• i=2, h=1 > h[1]=0，入栈 [1,2]
• i=3, h=0 < h[2]=1 → 弹出 2：左边界 1，右边界 3，宽度=3-1-1=1，面积=1×1=1
• i=3, h=0 = h[1]=0，入栈前先弹出 1：左边界 -1，右边界 3，宽度=3-(-1)-1=3，面积=0×3=0（面积 0 不影响最大）
• i=3, 栈空，入栈 [3]
• i=4, h=0 < h[3]=0，入栈前先弹出 3：左边界 -1，右边界 4，宽度=4-(-1)-1=4，面积=0×4=0
• i=4, 栈空，入栈 [4]
• 遍历结束，栈 [4]：高度 0，宽度 5-(-1)-1=5，面积 0
  最大面积 = 1（实际还有 i=2 时未计算？等一下，我们漏了在 i=2 时未触发计算，但遍历结束会算）

实际上更稳妥的做法是：在 heights 末尾加一个 0 高度，确保所有柱子出栈计算。
我们重新简算一下：
[1,0,1,0,0] 加尾 0 → [1,0,1,0,0,0]
栈变化：

• 0: 栈 [0]
• 1: h=0<1，弹出 0：左-1，右1，宽=1，面积=1
  栈空，入 1
• 2: h=1>0，入栈 [1,2]
• 3: h=0<1，弹出 2：左1，右3，宽=1，面积=1
  h=0=0，弹出 1：左-1，右3，宽=3，面积=0
  栈空，入 3
• 4: h=0=0，弹出 3：左-1，右4，宽=4，面积=0
  栈空，入 4
• 5: h=0<0，弹出 4：左-1，右5，宽=5，面积=0
  最大面积=1（第 0 行最大矩形面积 1）

第 1 行高度： [2,0,2,1,1] 加尾 0
栈过程：

• 0: [0]
• 1: h=0<2，弹出 0：左-1，右1，宽=1，面积=2
  栈空，入 1
• 2: h=2>0，入栈 [1,2]
• 3: h=1<2，弹出 2：左1，右3，宽=1，面积=2
  h=1>0，入栈 [1,3]
• 4: h=1<1，弹出 3：左1，右4，宽=2，面积=2
  h=1>0，入栈 [1,4]
• 5: h=0<1，弹出 4：左1，右5，宽=3，面积=3
  弹出 1：左-1，右5，宽=5，面积=0
  最大面积=3（但这里似乎不对，我们检查：实际最大矩形是第 1 行最后三列 2,1,1 高度？等一下，高度是 2,1,1，最大矩形是 min(2,1,1)×3=3？不对，应该是高度 1 的底边宽 3 面积 3，或者高度 2 的宽 1 面积 2，确实最大是 3。但示例答案是 6，说明在第 2 行会出现）

第 2 行高度： [3,1,3,2,2] 加尾 0
计算过程略（用单调栈），可得最大面积 = 6（对应最后两列高度 2,2 宽度 3，即 2×3=6；或者中间高度 3 宽度 2 得 6 一样）

第 3 行高度： [4,0,0,3,0] 加尾 0
最大面积 = 3（第 4 列高度 3 宽度 1）

最终最大面积 = max(1, 3, 6, 3) = 6。

7. 代码框架（Python）

def maximalRectangle(matrix):
    if not matrix or not matrix[0]:
        return 0
    m, n = len(matrix), len(matrix[0])
    heights = [0] * n
    max_area = 0
    
    for i in range(m):
        # 更新高度数组
        for j in range(n):
            if matrix[i][j] == '1':
                heights[j] += 1
            else:
                heights[j] = 0
        # 计算当前行的最大矩形面积
        max_area = max(max_area, largestRectangleArea(heights))
    
    return max_area

def largestRectangleArea(heights):
    heights = heights + [0]  # 末尾加0保证全部出栈
    stack = []
    max_area = 0
    for i in range(len(heights)):
        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)
    return max_area

8. 复杂度分析

• 时间复杂度：O(m×n)，因为每行处理 heights 数组和单调栈计算都是 O(n)。
• 空间复杂度：O(n)，用于 heights 数组和栈。

9. 总结

本题的关键在于：

1. 将二维矩阵按行转化为柱状图高度数组。
2. 对每一行用单调栈解法求最大矩形面积（第 84 题）。
3. 取所有行中的最大值。

这样我们就在 O(m×n) 时间内解决了问题。