线性动态规划：最大矩形

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

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

最大矩形的面积为 6（第二行和第三行中连续的三个 1 组成的矩形）。

解题思路
此问题可转化为多个 柱状图中最大矩形 问题的组合。具体步骤分解如下：

1. 预处理每一行的高度数组

   • 定义 height 数组，height[i][j] 表示从当前行向上连续 1 的个数（包括当前行）。
   • 例如，对上述矩阵：
     • 第一行：[1,0,1,0,0]
     • 第二行：[2,0,2,1,1]（第二行每个位置向上看，连续 1 的高度）
     • 第三行：[3,1,3,2,2]
     • 第四行：[4,0,0,3,0]

2. 对每一行应用“柱状图中最大矩形”算法

   • 使用单调栈法：遍历每个高度，维护一个单调递增栈，快速计算以当前高度为矩形高度的最大宽度。
   • 单调栈规则：
     • 栈存储下标，对应高度递增。
     • 当当前高度小于栈顶高度时，弹出栈顶，计算矩形面积：
       • 高度 = height[栈顶索引]
       • 宽度 = 当前索引 - 栈内前一个索引 - 1（若栈空则宽度为当前索引）
     • 遍历结束后，清空栈并计算剩余面积。

3. 示例演示（第三行高度数组 [3,1,3,2,2]）

   • 索引 0：栈空，入栈 0。
   • 索引 1：高度 1 < 3，弹出栈顶 0，计算面积：高度=3，宽度=1-0-1? 栈空则宽度=1，面积=3。
   • 索引 1：栈空，入栈 1。
   • 索引 2：高度 3 > 1，入栈 2。
   • 索引 3：高度 2 < 3，弹出栈顶 2，计算面积：高度=3，宽度=3-1-1=1，面积=3。
   • 索引 3：高度 2 > 1，入栈 3。
   • 索引 4：高度 2 = 2，入栈 4。
   • 遍历结束，清空栈：
     • 弹出 4：高度=2，宽度=5-3-1=1，面积=2。
     • 弹出 3：高度=2，宽度=5-1-1=3，面积=6（最大）。
     • 弹出 1：高度=1，宽度=5，面积=5。

4. 复杂度分析

   • 时间复杂度：O(m×n)，每行处理一次单调栈（O(n)）。
   • 空间复杂度：O(n)，用于存储高度数组和单调栈。

关键点总结

• 将二维问题转化为一维柱状图问题，逐行累积高度。
• 单调栈高效计算每个高度能扩展的最大宽度。
• 遍历所有行，取最大面积即为最终解。