线性动态规划：最大矩形

题目描述
给定一个仅包含 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：问题分析

最大矩形问题可以视为多个子问题的叠加：

• 若将矩阵的每一行视为一个基准，计算从该行向上延伸的“柱状图高度”，问题转化为柱状图中的最大矩形问题（即 LeetCode 84 题）。
• 例如，对于第 i 行，height[j] 表示从第 i 行第 j 列向上连续 1 的个数（包括第 i 行）。

步骤2：转换为柱状图最大矩形

以示例矩阵为例：

• 第 0 行：[1,0,1,0,0] → 高度 [1,0,1,0,0]
• 第 1 行：叠加上一行的高度（若当前为 1 则高度+1，否则重置为 0）：[2,0,2,1,1]
• 第 2 行：[3,1,3,2,2]
• 第 3 行：[4,0,0,3,0]

对每一行的高度数组，调用柱状图最大矩形算法。

步骤3：柱状图最大矩形算法（单调栈）

给定高度数组 heights，求最大矩形面积的方法：

1. 遍历每个柱子的高度，维护一个单调递增栈（存储索引）。
2. 当当前高度 < 栈顶高度时，说明栈顶柱子的右边界确定，弹出栈顶并计算面积：
   • 高度 = heights[stack.pop()]
   • 宽度 = 当前索引 i - 新栈顶索引 stack[-1] - 1（若栈为空则宽度为 i）
3. 在遍历结束后，用剩余栈中的索引计算面积（右边界为数组长度）。

示例：heights = [3,1,3,2,2]

• 索引 0：栈 [0]
• 索引 1：高度 1 < 3，弹出 0 → 高度=3，宽度=1-(-1)-1=1 → 面积=3
• 索引 1：栈 [1]
• 索引 2：栈 [1,2]
• 索引 3：高度 2 < 3，弹出 2 → 高度=3，宽度=3-1-1=1 → 面积=3
• 索引 3：栈 [1,3]
• 索引 4：栈 [1,3,4]
• 遍历结束：依次弹出计算：
  • 弹出 4：高度=2，宽度=5-3-1=1 → 面积=2
  • 弹出 3：高度=2，宽度=5-1-1=3 → 面积=6（最大）
  • 弹出 1：高度=1，宽度=5 → 面积=5
    最大面积为 6。

步骤4：整合算法

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

步骤5：复杂度分析

• 时间：O(行数 × 列数)，每行处理一次单调栈（O(列数)）。
• 空间：O(列数)，用于 height 数组和栈。

总结
通过将二维问题转化为一维柱状图最大矩形问题，并利用单调栈高效求解每一行的场景，可得到全局最大矩形面积。