Skip to content

Latest commit

 

History

History
99 lines (88 loc) · 3.19 KB

221. Maximal Square.md

File metadata and controls

99 lines (88 loc) · 3.19 KB
Raw

221. Maximal Square

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
  • 两种思路,两种思路去定义dp[y][x]
  • 暴力解法，dp[y][x] 意味着：从（0，0）到(y,x) 围成的正方形面积然后利用dp+计算面积求解.
  • 第二种dp dp[y][x] 意味着：在（y，x）且包含这点的最大的square的边，脑海里要想象一个图，四种case全都cover。

Explanation

  • brute force method is to check every start point with different size(like, size 1 square, 22, 33) (O(m*n)*min(m, n))
  • then check the square are all 1 O(m*n)
  • But there are some duplicate compuataion when we check size 3, since we already check size 2 square
  • So using dp here
  • image 1 , using image 2 info to calculate a sum(x:x+size, y:y+size)
  • image 2, start to build a dp which means sum(0:x, 0:y) 
class Solution {
    public int maximalSquare(char[][] matrix) {
        int m = matrix.length;
        if(m==0) return 0;
        int n = matrix[0].length;
        int[][] dp = new int[m+1][n+1];
        //i, j means sum of (0:i, 0:j)-- from image 2
        for(int i = 1; i<=m; i++){
            for(int j = 1; j<=n; j++){
                dp[i][j] = dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1]+matrix[i-1][j-1]-'0';
            }
        }
        int ans = 0;
        //the process is from image 1
        for(int i = 1; i<=m; i++){
            for(int j = 1; j<=n; j++){
                //check different size
                for(int k = Math.min(m-i+1, n-j+1); k>0; k--){
                    //here define k and i, j , tricky
                    int sum = dp[i+k-1][j+k-1]-dp[i+k-1][j-1]-dp[i-1][j+k-1]+dp[i-1][j-1];
                    if(sum==k*k){
                        ans = Math.max(sum, ans);
                    }
                }
            }
        }
        return ans;
        
    }
}

Solution 2:

  • dp o(n^n)
  • 为什么这里matrix[y][x]=0, 我们的dp[y][x]为0？反正法：如果不是0，那么图中第四种情况就不会得到1，而是其他
  • 更正: 讲义中方法2的最后一个case有错误，正确的值为：
  • dp[y-1][x] = 1; dp[y][x-1] = 1; dp[y-1][x-1] = 0; dp[y][x] = 1;
class Solution {
    public int maximalSquare(char[][] matrix) {
        int m = matrix.length;
        if(m==0) return 0;
        int n = matrix[0].length;
        int[][] dp = new int[m+1][n+1];
        int ans = 0;
        for(int i = 1 ; i<=m; i++){
            for(int j = 1; j<=n; j++){
                if(matrix[i-1][j-1]=='0')
                    dp[i][j] = 0;
                else{
                    dp[i][j] = Math.min(Math.min(dp[i-1][j], dp[i][j-1]), dp[i-1][j-1])+1;
                    
                    //System.out.println(dp[i][j]);
                    ans = Math.max(dp[i][j], ans);
                }
            }
        }
        return ans*ans;
    }
}

Similiar QUestion

  • 81 maxiam rectangle

Reference