力扣 221. 最大正方形

题目描述：

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

解析：

动态规划

1.dp[i][j]为存储到点(i,j)时以此为右下角的正方形个数
2.只有当前值为1时才可能构成正方形
3.在上面前提下,最左边和最右边都只能构成边长为1的正方形
4.边长多大还取决于其它三个点的值 所以这边取其最小值+1，有一个为0都不能扩大

Java:

class Solution {
    public int maximalSquare(char[][] matrix) {
        if(matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return 0;
        }
        int m = matrix.length, n = matrix[0].length;
        int[][] dp = new int[m][n];
        int maxSqueue = 0;
        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
                if(matrix[i][j] == '1') {
                    if(i == 0 || j == 0) {
                        dp[i][j] = 1;
                    } else {
                        dp[i][j] = Math.min(dp[i][j-1], Math.min(dp[i - 1][j], dp[i-1][j-1])) + 1;
                    }
                }
                maxSqueue = Math.max(maxSqueue, dp[i][j]);
            }
        }
        return maxSqueue * maxSqueue;
    }
}

JavaScript:

var maximalSquare = function(matrix) {
    if(matrix === null || matrix.length === 0 || matrix[0].length === 0) {
        return 0;
    }
    let m = matrix.length, n = matrix[0].length;
    let dp = Array(m + 1).fill(0).map(()=> Array(n + 1).fill(0));
    let maxSqueue = 0;
    for(let i = 0; i < m; i++) {
        for(let j = 0; j < n; j++) {
            if(matrix[i][j] == '1') {
                if(i === 0 || j === 0) {
                    dp[i][j] = 1;
                } else {
                    dp[i][j] = Math.min(dp[i][j-1], dp[i-1][j], dp[i-1][j-1]) + 1;
                }
            }
            maxSqueue = Math.max(maxSqueue, dp[i][j]);
        }
    }
    return maxSqueue * maxSqueue;
};