最大正方形

来源Leetcode第221题最大正方形

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

示例:

暴力遍历

如果当前节点是1就以此点为正方形的左上角，进行向右向下的遍历，在遍历时维护一个变量，当前正方形的边长和最大正方形的边长，如果新增加的行列均为1，则当前边长+1，直到检索到0，移动到下一点，并且更新最大正方形边长。

public int maximalSquare(char[][] matrix) {
    if(matrix.length == 0)
        return 0;
    int max = 0;  //记录最大边长
    int row = matrix.length;
    int col = matrix[0].length;
    for(int i = 0 ; i < row; i++){
        for(int j = 0 ; j < col; j++){
            if(matrix[i][j] == '1'){
                //从当前点开始搜索
                int curlen = 1;  //记录能组成的最大正方形边长
                boolean flag = true;
                while(curlen + i < row && curlen + j < col && flag){
                    //从当前点向右向下搜索
                    for(int k = j ; k <= curlen + j;k++){
                        if(matrix[i + curlen][k] == '0'){
                            flag = false;
                            break;
                        }
                    }
                    for(int k = i ; k <= curlen + i ; k++){
                        if(matrix[k][j + curlen] == '0'){
                            flag = false;
                            break;
                        }
                    }
                    if(flag) // 为真，增加搜索的边长
                        curlen++;
                }
                max = Math.max(max,curlen);
            }
        }
    }
    return max * max;
}

动态规划

来源

如题，动态规划方法的题解中，都会涉及到下列形式的代码：

1
2
3

if (grid(i, j) == 1) {
    dp(i, j) = min(dp(i-1, j), dp(i, j-1), dp(i-1, j-1)) + 1;
}

翻译成中文

若某格子值为 1 ，则以此为右下角的正方形的、最大边长为：上面的正方形、左面的正方形或左上的正方形中，最小的那个，再加上此格。

先来阐述简单共识

若形成正方形（非单 1），以当前为右下角的视角看，则需要：当前格、上、左、左上都是 1
可以换个角度：当前格、上、左、左上都不能受 0 的限制，才能成为正方形

public int maximalSquare(char[][] matrix) {
    // base condition
    if (matrix == null || matrix.length < 1 || matrix[0].length < 1) return 0;

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

    // 相当于已经预处理新增第一行、第一列均为0
//        int[][] dp = new int[height + 1][width + 1];
    int[] dp = new int[width + 1];
    int northwest = 0; // 西北角、左上角

//        for (int row = 0; row < height; row++) {
    for (char[] chars : matrix) {
        for (int col = 0; col < width; col++) {
            int nextNorthwest = dp[col + 1];
            if (chars[col] == '1') {
//                    dp[row + 1][col + 1] = Math.min(Math.min(dp[row + 1][col], dp[row][col + 1]), dp[row][col]) + 1;
                dp[col + 1] = Math.min(Math.min(dp[col], dp[col + 1]), northwest) + 1;

//                    maxSide = Math.max(maxSide, dp[row + 1][col + 1]);
                maxSide = Math.max(maxSide, dp[col + 1]);
            } else {
                dp[col + 1] = 0;
            }
            northwest = nextNorthwest;
        }
    }
    return maxSide * maxSide;
}