好的，我们这次来详细讲解 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
解释：最大矩形如图所示（右下角 2×3 的矩形区域）。

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

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

约束条件：

• rows == matrix.length
• cols == matrix[i].length
• 1 <= row, cols <= 200
• matrix[i][j] 为 '0' 或 '1'

2. 思路引导

这个问题如果直接暴力枚举所有矩形，复杂度会很高。
我们可以利用 动态规划 和 单调栈 来高效解决。

2.1 转化为已知问题

回想我们做过的 LeetCode 84 题：柱状图中最大的矩形，它是给定一个高度数组，求最大矩形面积。
本题可以转化为对每一行，计算以该行为底边的“柱状图”，然后调用 84 题的解法。

2.2 高度数组的构造

定义 height[i][j] 表示从当前行往上数，以 (i, j) 为底，连续的 '1' 的个数（包括当前行）。

例子：
对示例 1 的矩阵：

第 0 行：
["1","0","1","0","0"]
高度数组：[1, 0, 1, 0, 0]

第 1 行：
["1","0","1","1","1"]
如果该位置是 '1'，则高度 = 上一行同列高度 + 1，否则为 0。
得到：[2, 0, 2, 1, 1]

第 2 行：
["1","1","1","1","1"]
高度数组：[3, 1, 3, 2, 2]

第 3 行：
["1","0","0","1","0"]
高度数组：[4, 0, 0, 3, 0]

2.3 对每一行调用 84 题的单调栈解法

对每一行的高度数组，用单调栈方法求最大矩形面积：

单调栈思路回顾（84 题）：

• 遍历每个柱子的高度；
• 维护一个单调递增栈（存下标）；
• 当当前高度小于栈顶高度时，说明栈顶柱子的右边界确定，左边界是栈内前一个下标，计算面积；
• 在数组头尾加一个高度 0，方便处理边界。

3. 逐步推演示例

以第 2 行高度数组 [3, 1, 3, 2, 2] 为例，我们走一遍单调栈过程。

数组前后补 0：[0, 3, 1, 3, 2, 2, 0]，下标从 0 到 6。

栈初始放 -1 或先放 0（高度 0 的下标 0）。

步骤：

1. i=0, h=0，栈空 → 入栈 [0]
2. i=1, h=3，大于栈顶高度 0 → 入栈 [0,1]
3. i=2, h=1，小于栈顶高度 3 → 弹出栈顶 1（高度 3）：
   • 左边界 = 当前栈顶 0（高度 0），右边界 = i=2
   • 宽度 = 2 - 0 - 1 = 1
   • 面积 = 3 × 1 = 3
   • 栈变为 [0]
   • 现在 i=2, h=1 与栈顶高度 0 比较，大于 → 入栈 [0,2]
4. i=3, h=3，大于栈顶高度 1 → 入栈 [0,2,3]
5. i=4, h=2，小于栈顶高度 3 → 弹出栈顶 3（高度 3）：
   • 左边界 = 栈顶 2（高度 1），宽度 = 4 - 2 - 1 = 1
   • 面积 = 3 × 1 = 3
   • 栈 [0,2]
   • 现在 h=2 与栈顶高度 1 比较，大于 → 入栈 [0,2,4]
6. i=5, h=2，等于栈顶高度 2？其实可以入栈，但为了统一，我们规定严格小于才弹出，所以相等时可入栈（或弹出再算也行，但这里我们按标准单调递增栈，允许相等入栈）→ 入栈 [0,2,4,5]
7. i=6, h=0，小于栈顶高度 2 → 弹出栈顶 5（高度 2）：
   • 左边界 = 栈顶 4（高度 2），宽度 = 6 - 4 - 1 = 1
   • 面积 = 2 × 1 = 2
   • 栈 [0,2,4]
   • 比较 h=0 与栈顶高度 2 → 弹出 4（高度 2）：
     • 左边界 = 栈顶 2（高度 1），宽度 = 6 - 2 - 1 = 3
     • 面积 = 2 × 3 = 6
     • 栈 [0,2]
   • 比较 h=0 与栈顶高度 1 → 弹出 2（高度 1）：
     • 左边界 = 栈顶 0（高度 0），宽度 = 6 - 0 - 1 = 5
     • 面积 = 1 × 5 = 5
     • 栈 [0]
   • 比较 h=0 与栈顶高度 0 → 入栈？不，这里我们直接结束，因为栈顶是 0（高度 0），当前 h=0，可以不入栈，但算法里会继续弹出 0（高度 0）时宽度 = 6 - (-1) - 1 = 6，面积 0，不影响最大值。

最大面积在计算过程中出现的是 6。

4. 算法步骤总结

1. 如果矩阵为空，返回 0。
2. 初始化 rows, cols，初始化 height 数组长度为 cols，全 0。
3. 初始化 maxArea = 0。
4. 遍历每一行 i：
   • 更新 height[j]：如果 matrix[i][j] == '1'，则 height[j] += 1，否则 height[j] = 0。
   • 用单调栈法（84 题解法）计算当前 height 数组的最大矩形面积，更新 maxArea。
5. 返回 maxArea。

5. 代码实现（Python）

def maximalRectangle(matrix):
    if not matrix or not matrix[0]:
        return 0
    
    rows, cols = len(matrix), len(matrix[0])
    height = [0] * cols
    max_area = 0
    
    for i in range(rows):
        # 更新高度数组
        for j in range(cols):
            if matrix[i][j] == '1':
                height[j] += 1
            else:
                height[j] = 0
        
        # 调用84题解法：柱状图最大矩形
        stack = []
        # 在高度数组前后补0
        heights = [0] + height + [0]
        for k in range(len(heights)):
            while stack and heights[stack[-1]] > heights[k]:
                h = heights[stack.pop()]
                w = k - stack[-1] - 1
                max_area = max(max_area, h * w)
            stack.append(k)
    
    return max_area

6. 复杂度分析

• 时间复杂度：O(rows × cols)
  每行更新高度 O(cols)，每行单调栈处理 O(cols)，总体 O(rows × cols)。
• 空间复杂度：O(cols)
  用于存储高度数组和栈。

7. 关键点总结

• 将二维问题转化为多个一维柱状图最大矩形问题（84 题）。
• 高度数组的定义：从当前行往上连续的 '1' 数量。
• 单调栈技巧：前后补 0 处理边界，栈内存下标，保持高度递增。

这样，我们就循序渐进地解决了 LeetCode 85 题“最大矩形”。