221. 最大正方形

问题描述

在一个由 '0' 和 '1' 组成的二维二进制矩阵中，找出只包含 '1' 的最大正方形，并返回其面积。

示例：

输入: 
matrix = [["1","0","1","0","0"],
          ["1","0","1","1","1"],
          ["1","1","1","1","1"],
          ["1","0","0","1","0"]]

输出: 4
解释: 最大正方形是右下角的 2×2 区域，面积为 4。

算法思路

方法一：动态规划（推荐解法）

1. 定义状态：dp[i][j] 表示以 (i,j) 为 右下角 的最大正方形的边长
2. 状态转移方程：
   • 如果 matrix[i][j] == '0'，则 dp[i][j] = 0（无法形成正方形）
   • 如果 matrix[i][j] == '1'，则：

     dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1
     

     解释：当前位置能形成的最大正方形边长，取决于上方、左方和左上方三个位置的最小值加1
3. 边界条件：第一行和第一列直接取矩阵值（转为整数）
4. 实时更新最大边长，最后返回面积（边长²）

方法二：暴力枚举

1. 遍历每个位置作为正方形的左上角
2. 对每个位置，尝试从边长1开始逐步扩大正方形
3. 检查新扩大的边界是否全为’1’
4. 记录最大成功边长

代码实现

方法一：动态规划（推荐解法）

class Solution {
    /**
     * 找出二进制矩阵中只包含'1'的最大正方形面积
     * 
     * 核心思想：动态规划
     * dp[i][j] 表示以(i,j)为右下角的最大正方形边长
     * 状态转移：dp[i][j] = min(上, 左, 左上) + 1 （当matrix[i][j]=='1'时）
     * 
     * @param matrix 二维字符数组，包含'0'和'1'
     * @return 最大正方形的面积
     */
    public int maximalSquare(char[][] matrix) {
        // 边界检查
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return 0;
        }
        
        int rows = matrix.length;
        int cols = matrix[0].length;
        
        // dp[i][j] 表示以(i,j)为右下角的最大正方形边长
        int[][] dp = new int[rows][cols];
        
        // 记录最大边长
        int maxSide = 0;
        
        // 遍历矩阵每个位置
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                // 当前位置是'1'
                if (matrix[i][j] == '1') {
                    if (i == 0 || j == 0) {
                        // 边界情况：第一行或第一列
                        // 只能形成边长为1的正方形（如果当前是'1'）
                        dp[i][j] = 1;
                    } else {
                        // 一般情况：取三个相邻位置的最小值加1
                        // dp[i-1][j]   -> 上方
                        // dp[i][j-1]   -> 左方  
                        // dp[i-1][j-1] -> 左上方
                        dp[i][j] = Math.min(
                            Math.min(dp[i-1][j], dp[i][j-1]), 
                            dp[i-1][j-1]
                        ) + 1;
                    }
                    // 更新最大边长
                    maxSide = Math.max(maxSide, dp[i][j]);
                }
                // 如果matrix[i][j]=='0'，dp[i][j]保持为0（默认值）
            }
        }
        
        // 返回最大正方形的面积
        return maxSide * maxSide;
    }
}

方法二：空间优化的动态规划

class Solution {
    /**
     * 空间优化版：使用一维数组代替二维dp数组
     * 
     * 核心思想：由于dp[i][j]只依赖于上一行和当前行的前一个元素
     * 可以用一维数组滚动更新，同时用变量记录左上角的值
     * 
     * @param matrix 二维字符数组
     * @return 最大正方形的面积
     */
    public int maximalSquare(char[][] matrix) {
        // 边界检查
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return 0;
        }
        
        int rows = matrix.length;
        int cols = matrix[0].length;
        
        // dp[j] 表示当前行第j列的最大正方形边长
        int[] dp = new int[cols];
        
        // 记录最大边长
        int maxSide = 0;
        
        // 遍历每一行
        for (int i = 0; i < rows; i++) {
            // 记录左上角的值（上一行上一列的dp值）
            int prevDiagonal = 0; // dp[i-1][j-1]
            
            for (int j = 0; j < cols; j++) {
                // 保存当前dp[j]，它将成为下一个j的prevDiagonal
                int temp = dp[j];
                
                if (matrix[i][j] == '1') {
                    if (i == 0 || j == 0) {
                        // 边界情况
                        dp[j] = 1;
                    } else {
                        // dp[j] = min(上, 左, 左上) + 1
                        // dp[j]     -> 上方（上一行的值）
                        // dp[j-1]   -> 左方（当前行已计算的值）
                        // prevDiagonal -> 左上方（上一行上一列的值）
                        dp[j] = Math.min(
                            Math.min(dp[j], dp[j-1]), 
                            prevDiagonal
                        ) + 1;
                    }
                    // 更新最大边长
                    maxSide = Math.max(maxSide, dp[j]);
                } else {
                    // matrix[i][j]=='0'，无法形成正方形
                    dp[j] = 0;
                }
                
                // 更新prevDiagonal为当前的上一行值
                // 用于下一个j作为左上方的值
                prevDiagonal = temp;
            }
        }
        
        return maxSide * maxSide;
    }
}

算法分析

• 时间复杂度：

  • 方法一（二维DP）：O(m×n)
    • 需要遍历整个矩阵一次
  • 方法二（一维DP）：O(m×n)
    • 同样需要遍历整个矩阵一次

• 空间复杂度：

  • 方法一：O(m×n)
    • 需要二维dp数组存储所有状态
  • 方法二：O(n)
    • 只需要一维数组和几个变量

• 对比：

  方法	时间复杂度	空间复杂度	优点	缺点
  二维DP	O(mn)	O(mn)	逻辑清晰，易于理解	空间占用较大
  一维DP	O(mn)	O(n)	空间效率高，适合大矩阵	逻辑稍复杂

算法过程

输入矩阵：

[
 ['1','0','1','0','0'],
 ['1','0','1','1','1'], 
 ['1','1','1','1','1'],
 ['1','0','0','1','0']
]

动态规划过程（dp数组）

初始化：maxSide = 0

i=0 (第一行):
  j=0: '1' → dp[0][0]=1, maxSide=1
  j=1: '0' → dp[0][1]=0
  j=2: '1' → dp[0][2]=1, maxSide=1  
  j=3: '0' → dp[0][3]=0
  j=4: '0' → dp[0][4]=0

i=1 (第二行):
  j=0: '1' → dp[1][0]=1, maxSide=1
  j=1: '0' → dp[1][1]=0
  j=2: '1' → dp[1][2]=1, maxSide=1
  j=3: '1' → dp[1][3]=min(0,1,1)+1=1, maxSide=1
  j=4: '1' → dp[1][4]=min(0,0,1)+1=1, maxSide=1

i=2 (第三行):
  j=0: '1' → dp[2][0]=1, maxSide=1
  j=1: '1' → dp[2][1]=min(1,0,1)+1=1, maxSide=1
  j=2: '1' → dp[2][2]=min(1,0,1)+1=1, maxSide=1
  j=3: '1' → dp[2][3]=min(1,1,1)+1=2, maxSide=2
  j=4: '1' → dp[2][4]=min(1,1,2)+1=2, maxSide=2

i=3 (第四行):
  j=0: '1' → dp[3][0]=1
  j=1: '0' → dp[3][1]=0
  j=2: '0' → dp[3][2]=0
  j=3: '1' → dp[3][3]=min(2,0,1)+1=1
  j=4: '0' → dp[3][4]=0

最终 maxSide = 2, 面积 = 2² = 4

测试用例

public static void main(String[] args) {
    Solution solution = new Solution();
    
    // 测试用例1：示例输入
    char[][] matrix1 = {
        {'1','0','1','0','0'},
        {'1','0','1','1','1'},
        {'1','1','1','1','1'},
        {'1','0','0','1','0'}
    };
    System.out.println("Test 1: " + solution.maximalSquare(matrix1)); // 4
    
    // 测试用例2：全0矩阵
    char[][] matrix2 = {
        {'0','0'},
        {'0','0'}
    };
    System.out.println("Test 2: " + solution.maximalSquare(matrix2)); // 0
    
    // 测试用例3：全1矩阵
    char[][] matrix3 = {
        {'1','1'},
        {'1','1'}
    };
    System.out.println("Test 3: " + solution.maximalSquare(matrix3)); // 4
    
    // 测试用例4：单元素'1'
    char[][] matrix4 = {{'1'}};
    System.out.println("Test 4: " + solution.maximalSquare(matrix4)); // 1
    
    // 测试用例5：单元素'0'
    char[][] matrix5 = {{'0'}};
    System.out.println("Test 5: " + solution.maximalSquare(matrix5)); // 0
    
    // 测试用例6：空矩阵
    char[][] matrix6 = {};
    System.out.println("Test 6: " + solution.maximalSquare(matrix6)); // 0
    
    // 测试用例7：3x3最大正方形
    char[][] matrix7 = {
        {'1','1','1'},
        {'1','1','1'},
        {'1','1','1'}
    };
    System.out.println("Test 7: " + solution.maximalSquare(matrix7)); // 9
    
    // 测试用例8：L形结构
    char[][] matrix8 = {
        {'1','1','0','0'},
        {'1','1','0','0'},
        {'0','0','1','1'},
        {'0','0','1','1'}
    };
    System.out.println("Test 8: " + solution.maximalSquare(matrix8)); // 4
}

关键点

1. 状态定义：

   • 以右下角定义状态，使得状态转移只依赖于相邻三个位置
   • 这是动态规划中常见的"方向性"设计

2. 状态转移方程：

   • dp[i][j] = min(上, 左, 左上) + 1
   • 为什么取最小值？因为正方形要求四边相等，受限于最短的"边长"

3. 边界处理：

   • 第一行和第一列只能形成边长为1的正方形
   • 需要单独处理或在dp数组周围添加虚拟边界

4. 空间优化：

   • 由于只依赖上一行，可以用滚动数组优化
   • 需要额外变量保存左上角的值

5. 早期终止优化：

   • 理论上可以添加：如果剩余空间无法超过当前最大面积，则提前结束
   • 但实现复杂，通常不必要

常见问题

1. 为什么状态转移要取三个方向的最小值？

   • 要扩展一个正方形：上方决定了高度限制，左方决定了宽度限制，左上方决定了对角线限制
   • 最终能扩展的边长受限于这三个限制中最严格的那个

2. 能否用BFS/DFS解决？

   • 可以，但效率低：需要对每个’1’进行扩展检查
   • 时间复杂度可能达到O(m²n²)，远不如DP的O(mn)

3. 如果要求最大矩形怎么办？

   • 这是另一道经典题"最大矩形"（LeetCode 85）
   • 可以基于"柱状图中最大矩形"（LeetCode 84）的思想解决

4. 空间优化版中prevDiagonal的作用？

   • 在更新dp[j]之前，dp[j]存储的是上一行的值
   • 需要保存这个值作为下一个j的"左上方"参考
   • temp变量就是用来保存这个关键的对角线值

5. 如何处理字符和数字的转换？

   • Java中字符’1’-‘0’=1，‘0’-‘0’=0
   • 也可以用Character.getNumericValue(matrix[i][j])