1、前言

2、思路

这道题最重要的是 dp 数组的定义，dp[i][j] 定义为以 (i -1, j - 1) 为右下角的正方形的最大边长（记住是边长）。假设此时索引在 (i, j) 上且 matrix[i][j] == '1'，那么 dp[i][j] 的最大边长取决于 dp[i - 1][j]、dp[i][j - 1]、dp[i - 1][j - 1] 的最小值。为什么是最小值，因为以 (i, j) 作为正方形的话，必须取最小值才能构成。

3、代码

class Solution {
    public int maximalSquare(char[][] matrix) {
        if(matrix == null || matrix.length < 1 || matrix[0].length < 1){
            return 0;
        }

        int height = matrix.length;
        int width = matrix[0].length;
        int maxSide = 0;

        // 定义 dp[i][j] 表示右下角为 (i,j) 时最大正方形边长为
        // 相当于已经预处理新增第一行、第一列为0
        int[][] dp = new int[height + 1][width + 1];

        for(int row = 1; row <= height; row++){
            for(int col = 1; col <= width; col++){
                if(matrix[row - 1][col - 1] == '1'){
                    dp[row][col] = Math.min(Math.min(dp[row - 1][col], dp[row][col - 1]), dp[row - 1][col - 1]) + 1;
                    maxSide = Math.max(maxSide, dp[row][col]);
                }
            }
        }

        return maxSide * maxSide;
    }
}