动态规划解决最大矩形面积问题

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

[
  ["1","0","1","0","0"],
  ["1","0","1","1","1"],
  ["1","1","1","1","1"],
  ["1","0","0","1","0"]
]

最大矩形面积为 6（第二行和第三行的右侧 2×3 子矩阵）。

解题过程循序渐进讲解：

步骤 1：问题转化
此问题可转化为一系列直方图最大矩形面积子问题。

• 从第一行开始，将每一行视为一个直方图的底部，矩阵中从该行向上连续的 1 的数量作为直方图的高度。
• 例如，对第一行 ["1","0","1","0","0"]，高度数组为 [1,0,1,0,0]。
• 对第二行，累加上一行的值：若当前为 "1"，高度加 1；若为 "0"，高度归零。
• 通过逐行计算高度数组，将二维问题化为一维直方图最大矩形面积问题。

步骤 2：计算高度数组
定义一个数组 heights，长度等于矩阵列数，初始为 0。
遍历每一行时更新：

• 若 matrix[i][j] == '1'，则 heights[j] += 1。
• 若 matrix[i][j] == '0'，则 heights[j] = 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]

步骤 3：对每个高度数组求最大矩形面积
转化为经典问题：给定一个整数数组 heights，表示直方图各柱高度，求能勾勒出的最大矩形面积。

• 用单调栈解法可在 O(n) 时间内求解。
• 核心思想：对每个柱子，找出其左右第一个比它矮的柱子位置，确定以该柱子为高的矩形宽度。

单调栈算法细节：

1. 栈中存储下标，保持对应高度单调递增。
2. 遍历每个柱子：
   • 若当前高度 ≥ 栈顶高度，入栈。
   • 否则，弹出栈顶，计算以该弹出柱子为高的矩形面积：
     • 高度 = heights[pop_index]
     • 右边界 = 当前索引 i（第一个比它矮的右柱）
     • 左边界 = 新栈顶索引（弹出后栈顶，第一个比它矮的左柱）
     • 宽度 = 右边界 - 左边界 - 1
     • 面积 = 高度 × 宽度
3. 遍历结束后，栈中剩余柱子依次弹出计算（右边界视为数组长度 n）。
   例如，对 heights = [3,1,3,2,2]：

• 计算过程略，可得最大面积 5（以高度 3 的柱子为高，宽度受限，实际最大矩形由高度 2 的三个连续柱子组成 2×3=6）。

步骤 4：整合求解
对每一行的 heights 数组，调用单调栈算法求最大面积，记录全局最大值。
时间复杂度 O(行数 × 列数)，空间复杂度 O(列数)。

举例说明完整流程：
以示例矩阵第 2 行对应的 heights = [3,1,3,2,2] 为例，单调栈计算步骤：

• 索引 0（高 3）入栈。
• 索引 1（高 1）：高 3 弹出，左边界 -1，右边界 1，宽度 1，面积 3×1=3。
• 索引 1 入栈，栈 [1]。
• 索引 2（高 3）入栈，栈 [1,2]。
• 索引 3（高 2）：高 3 弹出，左边界 1，右边界 3，宽度 1，面积 3×1=3。
• 索引 3 高 2 与栈顶高 1 比较，仍入栈，栈 [1,3]。
• 索引 4（高 2）入栈，栈 [1,3,4]。
• 遍历结束，依次弹出：
  • 索引 4（高 2），左边界 3，右边界 5，宽度 1，面积 2。
  • 索引 3（高 2），左边界 1，右边界 5，宽度 3，面积 6 ← 最大值。
  • 索引 1（高 1），左边界 -1，右边界 5，宽度 5，面积 5。
    最大面积为 6，与示例一致。

步骤 5：代码框架（Python）

def maximalRectangle(matrix):
    if not matrix:
        return 0
    rows, cols = len(matrix), len(matrix[0])
    heights = [0] * cols
    max_area = 0
    
    for i in range(rows):
        for j in range(cols):
            heights[j] = heights[j] + 1 if matrix[i][j] == '1' else 0
        
        # 单调栈求直方图最大面积
        stack = []
        for k in range(cols + 1):
            h = heights[k] if k < cols else 0
            while stack and h < heights[stack[-1]]:
                height = heights[stack.pop()]
                left = stack[-1] if stack else -1
                width = k - left - 1
                max_area = max(max_area, height * width)
            stack.append(k)
    
    return max_area