221. Maximal Square

LeetCode Link

题目截图

题解方式 DP

public int maximalSquare(char[][] matrix) {
    if (matrix == null || matrix.length == 0 
            || matrix[0] == null || matrix[0].length == 0) {
        return 0;
    }
    
    int maximalEdge = 0;
    int rows = matrix.length;
    int cols = matrix[0].length;
    int[][] dp = new int[rows + 1][cols + 1];

    for (int i = 0; i < matrix.length; i++) {
        for (int j = 0; j < matrix[i].length; j++) {
            if (matrix[i][j] == '0') {
                continue;
            }
            dp[i + 1][j + 1] = Math.min(Math.min(dp[i+1][j], dp[i][j+1]), dp[i][j]) + 1;
            maximalEdge = Math.max(maximalEdge, dp[i + 1][j + 1]);
        }
    }
    
    return maximalEdge * maximalEdge;
}