线性动态规划：统计全为1的最大子矩形面积

这道题目是这样描述的：给定一个仅包含0和1的二维矩阵，要求找出其中全由1组成的最大子矩形，并返回其面积。例如，矩阵如下：

1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0

其中全1的最大子矩形是右下角的2x3矩形，面积为6。这道题是“最大矩形”问题的核心，我们可以通过线性动态规划的思想，将其转化为一系列“柱状图中的最大矩形”子问题来解决。

下面我为你详细讲解解题步骤，确保你能跟上每一步的思路。

第一步：理解问题与核心转化

我们需要在一个二维0-1矩阵中，找到全部由1构成的最大矩形。一个直接的想法是枚举所有可能的矩形，但那样时间复杂度会达到O(m²n²)，在矩阵较大时不可行。

高效的做法是：逐行考虑，将每一行当作一个柱状图的底部。具体来说：

• 对于第i行，我们计算一个高度数组height[j]，表示从当前行开始，向上连续有多少个连续的1（包含当前行）。
• 这样，对于每一行，我们就得到了一个柱状图，问题转化为：在柱状图中，找出最大矩形的面积。
• 对所有行都计算并更新最大面积，最终得到答案。

例如，对于上面矩阵的第2行（索引从0开始，即1 0 1 1 1），向上连续的1的个数为：

• 第0列：向上连续1的个数是2（本行1，上一行1）
• 第1列：0（本行是0，重置为0）
• 第2列：2（本行1，上一行1）
• 第3列：2（本行1，上一行1）
• 第4列：2（本行1，上一行1）
  对应的柱状图高度为[2,0,2,2,2]，其最大矩形面积是6（由最后三个高度为2的柱子组成，宽度为3，面积2×3=6）。

第二步：柱状图中最大矩形的解法（单调栈）

对于一行得到的height数组，如何快速求出最大矩形面积呢？这是经典问题，可以用单调递增栈在线性时间内解决。

单调栈算法步骤：

1. 在height数组的末尾添加一个高度0，确保最终所有柱子都能被处理。
2. 维护一个栈，栈中存放柱子的索引，且对应的高度是单调递增的。
3. 遍历每个柱子（索引j，高度h = height[j]）：
   • 如果栈为空或当前高度h >= height[栈顶索引]，则将j入栈。
   • 否则，不断弹出栈顶元素，每次弹出一个索引idx，它的高度height[idx]就是矩形的高度。此时，矩形的宽度 = j - 栈顶索引 - 1（栈为空时宽度为j）。计算面积 = 高度 × 宽度，更新最大面积。
4. 遍历结束后，栈中剩余的柱子依次弹出并计算面积（此时右边界是数组长度n）。

例子：height = [2,0,2,2,2]，计算过程：

• 遍历索引0（高度2）：栈空，入栈[0]
• 索引1（高度0）：0 < 2，弹出栈顶0，栈空，宽度=1，面积=2×1=2
  • 入栈1
• 索引2（高度2）：栈顶索引1对应高度0，2>=0，入栈[1,2]
• 索引3（高度2）：栈顶高度2，入栈[1,2,3]
• 索引4（高度2）：入栈[1,2,3,4]
• 最后加一个高度0，索引5：
  • 弹出4，高度2，栈顶3，宽度=5-3-1=1，面积2
  • 弹出3，高度2，栈顶2，宽度=5-2-1=2，面积4
  • 弹出2，高度2，栈顶1，宽度=5-1-1=3，面积6
  • 弹出1，高度0，栈空，宽度=5，面积0
    最大面积为6。

第三步：整合为二维动态规划

现在，我们只需逐行更新height数组，并对每一行调用单调栈算法。

具体步骤：

1. 初始化一个数组height，长度等于列数n，所有元素为0。
2. 遍历每一行i（0到m-1）：
   • 对每一列j，如果matrix[i][j] == '1'，则height[j] += 1；否则height[j] = 0。
   • 用单调栈算法计算当前height数组对应的最大矩形面积，更新全局最大面积。
3. 返回全局最大面积。

复杂度分析：

• 遍历每一行O(m)，每行单调栈处理O(n)，总时间复杂度O(m×n)。
• 空间复杂度O(n)，用于存储height数组和单调栈。

第四步：示例推演

以初始矩阵为例：

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

逐行计算height和最大面积：

• 第0行后：height = [1,0,1,0,0]，单调栈得最大面积1（第一个或第三个柱子，面积1×1=1）。
• 第1行后：height = [2,0,2,1,1]，单调栈计算：
  • 遍历[2,0,2,1,1,0]，最大面积出现在最后两个1，宽度2，高度1，面积2，但更大会在弹出高度2时，宽度1，面积2。实际最大是3（最后两个1加上前面的2？重新算：正确单调栈过程略），得到面积3（由高度2、1、1组成的矩形？注意高度不一致，需用单调栈准确计算，这里不展开，但结果应更新为3）。
• 第2行后：height = [3,1,3,2,2]，单调栈得最大面积6（由后三个高度2、2、2组成，但实际高度是3,1,3,2,2，最大面积是3×2=6？不，准确计算：单调栈可得出面积6，对应子矩阵是右下角2行3列）。
• 第3行后：height = [4,0,0,3,0]，最大面积是3（最后一列高度3，宽度1）。
  最终全局最大面积是6。

第五步：代码实现（伪代码）

def maximalRectangle(matrix):
    if not matrix:
        return 0
    m, n = len(matrix), len(matrix[0])
    height = [0] * n
    max_area = 0
    
    for i in range(m):
        for j in range(n):
            # 更新height数组
            if matrix[i][j] == '1':
                height[j] += 1
            else:
                height[j] = 0
        
        # 单调栈求当前行height的最大矩形面积
        stack = []
        for j in range(n + 1):
            h = height[j] if j < n else 0
            while stack and height[stack[-1]] > h:
                idx = stack.pop()
                height_idx = height[idx]
                width = j if not stack else j - stack[-1] - 1
                max_area = max(max_area, height_idx * width)
            stack.append(j)
    
    return max_area

第六步：总结与扩展

这道题的核心是将二维问题转化为一维柱状图问题，再通过单调栈高效求解。这种转化思想在很多二维动态规划问题中都很常见，比如“最大正方形”也可以用类似思想。

你可以尝试的变种：

• 如果矩阵中的元素是整数，求数值和最大的子矩形（可以用类似思想结合Kadane算法）。
• 如果要求矩形是正方形，则可用动态规划直接以dp[i][j]表示以(i,j)为右下角的最大正方形边长。

通过这道题，你不仅能掌握单调栈的应用，还能深化对“降维”动态规划策略的理解。