221. Maximal Square

221. Maximal Square

Question

Given a 2D binary matrix filled with 0’s and 1’s, find the largest square containing only 1’s and return its area.

Example:

Input:

1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0

Output: 4

Thinking:

• Method 1：dp
  • dp的每一个位置存储正方形边长的最大值。
  • 当当前位置为0， 跳过。
  • 当前位置为1
    • 左，左上，上均大于0：更新为三者最小值+1。
    • 其中包含0：更新为1。

class Solution {
    public int maximalSquare(char[][] matrix) {
        if(matrix == null || matrix.length == 0) return 0;
        int height = matrix.length, width = matrix[0].length;
        int[][] dp = new int[height][width];
        int result = 0;
        for(int i = 0; i < height; i++)
            if(matrix[i][0] == '1'){
                dp[i][0] = 1;
                result = Math.max(result, 1);
            }
        for(int i = 0; i < width; i++)
            if(matrix[0][i] == '1'){
                dp[0][i] = 1;
                result = Math.max(result, 1);
            }
        for(int i = 1; i < height; i++){
            for(int j = 1; j< width; j++){
                if(matrix[i][j] == '0') continue;
                int left = dp[i][j - 1];
                int up = dp[i - 1][j];
                int left_up = dp[i - 1][j - 1];
                if(left > 0 && up > 0 && left_up > 0){
                    dp[i][j] = Math.min(left, Math.min(up, left_up)) + 1;
                }else
                    dp[i][j] = 1;
                result = Math.max(result, dp[i][j]);
            }
        }
        return result * result;
    }
}

二刷

1. 原来还是想要用dp来做，用每一个位置存储面积，实际上应该存储边长更为合适。
2. 参考了一刷，如果左，上，左上为0，则当前点为0，不然取出三个值中的最小值 + 1。

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

Third time

1. Still use the same method, without hint.
2. Optimized the solution.

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