LeetCode 85. 最大矩形

题目描述
给定一个仅包含 0 和 1 的二进制矩阵 matrix，找出其中只包含 1 的最大矩形，并返回其面积。

例如：

输入：matrix = [["1","0","1","0","0"],
               ["1","0","1","1","1"],
               ["1","1","1","1","1"],
               ["1","0","0","1","0"]]
输出：6
解释：最大矩形如上图所示，面积为 6。

解题思路

这个问题可以转化为 LeetCode 84. 柱状图中最大的矩形（你已学过）的多次应用。
核心思想是：以每一行为基准，计算当前行及其上方行构成的“柱状图高度”，然后对每一行应用“柱状图最大矩形”的单调栈解法。

逐步讲解

步骤 1：将矩阵转化为柱状图高度

对于每一行 row，我们维护一个数组 heights：

• heights[j] 表示从当前行 row 开始，向上连续 1 的个数（包含当前行）。
• 如果 matrix[row][j] == '0'，则 heights[j] = 0（因为柱子中断了）。
• 如果 matrix[row][j] == '1'，则 heights[j] = heights[j] + 1（累加上一行的高度）。

例如：

矩阵：
1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0

第 0 行 heights: [1,0,1,0,0]
第 1 行 heights: [2,0,2,1,1]
第 2 行 heights: [3,1,3,2,2]
第 3 行 heights: [4,0,0,3,0]

步骤 2：对每一行的 heights 求最大矩形面积

利用 单调栈（Monotonic Stack）算法，可以在 O(n) 时间内求出柱状图最大矩形面积。
具体方法（复习 LeetCode 84）：

1. 遍历柱状图 heights，维护一个单调递增栈（存下标）。
2. 对于每个柱子 heights[i]，如果它比栈顶柱子低，就弹出栈顶，计算以弹出柱子为高的最大矩形面积：
   • 高度 = heights[弹出下标]
   • 右边界 = i - 1
   • 左边界 = 弹出后栈顶下标 + 1（栈为空时左边界为 0）
   • 面积 = 高度 × (右边界 - 左边界 + 1)
3. 遍历完后，若栈非空，同样方式弹出计算。

步骤 3：整体过程

1. 初始化 heights 数组长度为 n（矩阵列数），全为 0。
2. 遍历矩阵的每一行：
   • 更新 heights（当前行是 '1' 则加 1，否则归零）。
   • 对当前 heights 用单调栈求最大矩形面积。
   • 更新全局最大面积。
3. 返回全局最大面积。

例子模拟
以第 2 行为例（heights = [3,1,3,2,2]）：

柱状图：
下标 0: 高度 3
下标 1: 高度 1
下标 2: 高度 3
下标 3: 高度 2
下标 4: 高度 2

单调栈过程：

• i=0：栈空 → 入栈 [0]
• i=1：高度 1 < 3，弹出 0，计算面积：高度 3 × (1-0-1+1? 不，这里右边界=0，左边界=0 → 宽=1 → 面积=3)
  实际细节：弹出 0 时，栈空，左边界=0，右边界=i-1=0，面积=3×1=3
  入栈 [1]
• i=2：高度 3 > 1 → 入栈 [1,2]
• i=3：高度 2 < 3 → 弹出 2，左边界=栈顶1的下标+1=2，右边界=2，面积=3×1=3 → 栈 [1]，高度 2 > 1 → 入栈 [1,3]
• i=4：高度 2 = 2 → 入栈 [1,3,4]
  遍历结束，栈非空：
  弹出 4：左边界=3+1=4，右边界=4 → 面积=2×1=2
  弹出 3：左边界=1+1=2，右边界=4 → 面积=2×3=6
  弹出 1：栈空，左边界=0，右边界=4 → 面积=1×5=5
  最大面积 = max(3,3,2,6,5) = 6

代码框架（Python）

def maximalRectangle(matrix):
    if not matrix:
        return 0
    
    rows, cols = len(matrix), len(matrix[0])
    heights = [0] * (cols + 1)  # 多一位方便单调栈处理
    max_area = 0
    
    for row in range(rows):
        # 更新 heights
        for col in range(cols):
            if matrix[row][col] == '1':
                heights[col] += 1
            else:
                heights[col] = 0
        
        # 单调栈求最大矩形
        stack = []
        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

复杂度分析

• 时间：O(rows × cols)，每行处理 heights 和单调栈各 O(cols)。
• 空间：O(cols)，用于 heights 和栈。

核心思想总结
将二维矩阵逐行压缩成一维柱状图，多次利用 单调栈求柱状图最大矩形 的算法，从而高效求解原问题。