LeetCode 85. 最大矩形算法解析与 Java 实现

题目描述

给定一个仅包含 0 和 1、大小为 rows x cols 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。

示例 1： 输入：matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]] 输出：6 解释：最大矩形如上图所示。

示例 2： 输入：matrix = [["0"]] 输出：0

示例 3： 输入：matrix = [["1"]] 输出：1

提示： rows == matrix.length cols == matrix[0].length 1 <= rows, cols <= 200 matrix[i][j] 为 '0' 或 '1'

解题思路

首先创建一个与输入矩阵大小相同的 left 矩阵，left[i][j] 的含义是以第 i 行第 j 列为终点，从左往右连续的 1 的个数（即当前位置所在行，向左延伸的最大宽度）。例如，若某行是 ['1','1','0','1','1','1']，则对应的 left 行数据为 [1,2,0,1,2,3]。

遍历矩阵中的每个位置 (i,j)，若该位置是 1（有效位置），则以它作为矩形的右下角，向上（行号从 i-1 到 0）逐层遍历拓展矩形的高度：

1. 每层都取当前层 left[k][j] 与之前记录的宽度的最小值（保证矩形的宽度在纵向拓展中是有效的，即所有层都包含足够的连续 1）；
2. 计算当前纵向高度（i - k + 1）与有效宽度的乘积（即当前矩形面积）；
3. 不断更新最大面积值，最终得到整个矩阵中的最大矩形面积。

算法思路

1. 预处理阶段

• 遍历每一行，对于每个位置 (i,j)，若 matrix[i][j] 为 1，则 left[i][j] = (j==0 ? 0 : left[i][j-1]) + 1（左边位置的连续 1 个数加 1，若 j 是行首则直接为 1）；
• 若 matrix[i][j] 为 0，则 left[i][j] 保持为 0（无连续 1，无法构成矩形的右边界）。

2. 面积计算阶段

• 遍历每个有效位置 (i,j)（matrix[i][j] 为 1），初始化宽度为 left[i][j]（当前行的最大有效宽度）；
• 向上遍历每一行 k（从 i-1 到 0），更新有效宽度为 Math.min(width, left[k][j])（纵向所有行的最小有效宽度，保证矩形的完整性）；
• 计算当前矩形面积 (i - k + 1) * width（高度 × 有效宽度），并更新全局最大面积；
• 最终返回全局最大面积 ret。

Java 代码

class Solution {
    public int maximalRectangle(char[][] matrix) {
        int m = matrix.length;
        if (m == 0) {
            return 0;
        }
        int n = matrix[0].length;
        int[][] left = new int[m][n];

        
         (   ; i < m; i++) {
             (   ; j < n; j++) {
                 (matrix[i][j] == ) {
                    left[i][j] = (j ==  ?  : left[i][j - ]) + ;
                }
            }
        }

           ;
        
         (   ; i < m; i++) {
             (   ; j < n; j++) {
                 (matrix[i][j] == ) {
                    ;
                }
                   left[i][j];
                   width;
                
                 (   i - ; k >= ; k--) {
                    width = Math.min(width, left[k][j]);
                    area = Math.max(area, (i - k + ) * width);
                }
                ret = Math.max(ret, area);
            }
        }
         ret;
    }
}