线性动态规划：最大矩形（Maximum Rectangle）

题目描述

给你一个仅由 0 和 1 组成的二维矩阵，请你找出其中只包含 1 的最大矩形，并返回该矩形的面积。

例如，给定矩阵：

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

最大矩形如第二行第三列开始的 2×3 子矩阵（面积为6）。

解题思路

这个问题可以分解为多个子问题。核心想法是：对于每一行，我们可以将它看作一个以该行为底边的直方图，然后利用“柱状图中最大的矩形”问题的解法来求解当前行作为底边的最大矩形面积。

具体步骤：

1. 预处理每一行的高度：对于矩阵中的每一行，计算一个高度数组 heights，其中 heights[j] 表示从当前行向上连续 1 的个数（包含当前行）。如果当前行某列是 '0'，则高度重置为 0。
2. 对每一行应用柱状图最大矩形算法：将当前行的 heights 数组看作一个直方图，利用单调栈算法（或动态规划扩展法）求出以该行为底边的最大矩形面积。
3. 全局最大值：遍历所有行，更新最大面积。

这样，二维问题就转化成了一维的直方图最大矩形问题。

详细步骤

步骤1：理解“柱状图中最大的矩形”问题

给定一个非负整数数组 heights，表示直方图每根柱子的高度，求直方图中最大矩形的面积。

例如，heights = [2, 1, 5, 6, 2, 3]：

• 最大矩形是高度为 5 和 6 的两根柱子组成的宽为 2 的矩形，面积 = 5 × 2 = 10。

解法（单调栈）：

• 遍历每根柱子，维护一个单调递增栈（存储索引）。
• 当遇到当前柱子高度小于栈顶柱子高度时，说明找到了栈顶柱子右边界，同时栈顶的下一个元素是其左边界。
• 弹出栈顶，计算以其高度为矩形高度的最大宽度：宽度 = 当前索引 - 栈顶的下一个索引 - 1（若栈为空，则左边界为 -1）。
• 更新最大面积。
• 遍历结束后，再处理栈中剩余柱子（右边界为数组长度）。

时间复杂度 O(n)。

步骤2：应用到二维矩阵

对于矩阵的每一行 i，计算 heights 数组：

• 如果 matrix[i][j] == '1'，则 heights[j] += 1（累加之前行的高度）。
• 如果 matrix[i][j] == '0'，则 heights[j] = 0（因为连续性被破坏）。

这样，heights[j] 表示以 (i, j) 为底边向上连续 1 的高度。

步骤3：算法流程

1. 初始化 heights 数组为全 0，长度为列数 n。
2. 遍历每一行 i：
   • 更新 heights 数组：heights[j] = matrix[i][j] == '1' ? heights[j] + 1 : 0。
   • 对 heights 数组使用单调栈算法，计算以当前行为底边的最大矩形面积 area。
   • 更新全局最大面积 maxArea = max(maxArea, area)。
3. 返回 maxArea。

示例演算

对于上述示例矩阵：

第一行：

• heights = [1, 0, 1, 0, 0]
• 柱状图最大矩形面积：高度为 1 的柱子（索引 0 或 2），面积 = 1 × 1 = 1。

第二行：

• 更新 heights：在原有基础上累加（遇到 0 则清零） → [2, 0, 2, 1, 1]
• 柱状图：[2, 0, 2, 1, 1]
• 最大矩形：高度 2 的柱子（索引 0 或 2），但由于中间有 0 隔开，只能单独形成宽为 1 的矩形，面积 = 2 × 1 = 2。

第三行：

• 更新 heights：[3, 1, 3, 2, 2]
• 柱状图：[3, 1, 3, 2, 2]
• 单调栈过程：
  • 索引 0（高 3）入栈。
  • 索引 1（高 1）小于栈顶 3，弹出 0，计算面积：高度 3，宽度 1 - (-1) - 1 = 1，面积 3。
  • 索引 1 入栈。
  • 索引 2（高 3）大于栈顶 1，入栈。
  • 索引 3（高 2）小于栈顶 3，弹出 2，计算面积：高度 3，宽度 3 - 1 - 1 = 1，面积 3。
  • 现在栈顶为索引 1（高 1）小于 2，弹出 1，计算面积：高度 1，宽度 3 - (-1) - 1 = 3，面积 3。
  • 索引 3 入栈。
  • 索引 4（高 2）等于栈顶 2，入栈（或弹出再入栈，均可）。
  • 遍历结束，处理栈中剩余：
    • 弹出 4（高 2），宽度 5 - 3 - 1 = 1，面积 2。
    • 弹出 3（高 2），宽度 5 - 1 - 1 = 3，面积 6（最大）。
    • 弹出栈底索引 ?（已空）。
• 最大面积 = 6。

第四行：

• 更新 heights：[4, 0, 0, 3, 0]
• 最大矩形面积可能来自高度 3（索引 3），宽 1，面积 3。

全局最大面积 = 6。

代码实现（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):
        # 更新 heights 数组
        for j in range(cols):
            heights[j] = heights[j] + 1 if matrix[i][j] == '1' else 0
        
        # 单调栈求直方图最大矩形
        stack = []
        for idx, h in enumerate(heights + [0]):  # 末尾加0确保所有柱子被处理
            while stack and heights[stack[-1]] > h:
                height = heights[stack.pop()]
                width = idx if not stack else idx - stack[-1] - 1
                max_area = max(max_area, height * width)
            stack.append(idx)
    
    return max_area

复杂度分析

• 时间复杂度：O(m × n)，其中 m 是行数，n 是列数。因为每一行都要遍历一次 heights 数组进行更新和单调栈处理（单调栈处理 heights 是 O(n)）。
• 空间复杂度：O(n)，用于 heights 数组和单调栈。

总结

该问题通过逐行构建直方图，并利用单调栈高效求解直方图最大矩形，从而将二维问题转化为一维问题。关键在于理解 heights 数组的含义以及单调栈的运作机制。