221. Maximal Square

三刷 07/2022

Version #1 1D DP

Time O(MN)

Space O(N)

Runtime: 12 ms, faster than 26.14% of Java online submissions for Maximal Square.

Memory Usage: 57.4 MB, less than 73.58% of Java online submissions for Maximal Square.

class Solution {

    public int maximalSquare(char[][] matrix) {

        // max side length with (y, x) as the bottom right cornor of the square

        int[] dp = new int[matrix[0].length];

        int max = 0;

        for (int y = 0; y < matrix.length; y++) {

            int[] ndp = new int[matrix[0].length];

            for (int x = 0; x < matrix[0].length; x++) {

                if (matrix[y][x] == '0') {

                    continue;

                }

                if (y == 0 || x == 0) {

                    ndp[x] = 1;

                } else {

                    ndp[x] = 1 + Math.min(ndp[x - 1], Math.min(dp[x], dp[x - 1]));

                }

                max = Math.max(max, ndp[x]);

            }

            dp = ndp;

        }

        return max * max;

    }

}

一刷
side length边长
public class Solution {
    /**
     * @param matrix: a matrix of 0 and 1
     * @return: an integer
     */
    public int maxSquare(int[][] matrix) {
        // write your code here
        if (matrix == null || matrix.length == 0 || matrix[0] == null || matrix[0].length == 0) return 0;
        int rows = matrix.length;
        int cols = matrix[0].length;
        int maxLength = 0;
        //dp[x][y] is the maximum side length of the square whose left down corner is matrix[x][y]
        int[][] dp = new int[2][cols];
        for (int x = 0; x < rows; x++) {
            for (int y = 0; y < cols; y++) {
                //System.out.println(x + " " + y);
                if (x == 0 || y == 0) {
                    dp[x % 2][y] = matrix[x][y];
                } else if (matrix[x][y] == 1){
                    dp[x % 2][y] = 1 + Math.min(dp[(x - 1) % 2][y - 1], Math.min(dp[(x - 1) % 2][y], dp[x % 2][y - 1]));
                } else {
                    dp[x % 2][y] = 0;
                }
                maxLength = Math.max(dp[x % 2][y], maxLength);
            }
        }
        return maxLength * maxLength;
    }
}

二刷
空间未优化版
Space O(n^2)
 53.84 %
public class Solution {
    public int maximalSquare(char[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0] == null || matrix[0].length == 0) return 0;
        int max = 0;
        int rows = matrix.length, cols = matrix[0].length;
        int[][] dp = new int[rows][cols];
        for (int i = 0; i < rows; i++) {
            if (matrix[i][0] == '1') {
                dp[i][0] = 1;
                max = 1;
            }
        }
        for (int j = 1; j < cols; j++) {
            if (matrix[0][j] == '1') {
                dp[0][j] = 1;
                max = 1;
            }
        }
        for (int i = 1; i < rows; i++) {
            for (int j = 1; j < cols; j++) {
                if (matrix[i][j] == '1') {
                    dp[i][j] = Math.min(Math.min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1;
                    max = Math.max(max, dp[i][j]);
                }
            }
        }
        return max * max;
    }
}

Rolling Array
15.08 %
Space O(n)
写了一个bug
当matrix[i][j] == '0' 的时候，因为原来是二维默认初始值为0，所以不用处理
但是这里的array要reuse所以必须要置零

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