LeetCode——Maximal Square/二维矩阵最大正方形面积

Q:给定一个包含0和1的二维二进制矩阵,找出只包含1的最大正方形并返回其面积。
Example:

Input:
1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0

Output: 4

A:引用:https://blog.csdn.net/fly_fly_zhang/article/details/90637370
我们初始化一个二维矩阵dp, dp [ i ] [ j ] 表示以它为右下角的最大正方形边长。遍历原矩阵,每找到一个1,就求以它为右下角的最大正方形边长。
正方形的判断是一个从小到大的过程:
先看一个节点是否为1;
再看2/2范围是否满足条件。
依次,直到n/
n范围是否满足条件。
由此,这是后一个结果是否成立基于前一个结果的成立 ,因此使用dp处理。
dp[i][j] 角标的左边还有上边也就是以其为原点的第二象限,实际上已经是已知的。因此我们将其设置为正方形的右下角,恰是应用了已经条件。
而其它三个顶点的位置,实际上可以根据和它相邻的已推算处的正方形边长得到。其存在以下公式:
\[DP[i][j] = min(DP[i-1][j-1], DP[i-1][j], DP[i, j-1]) + 1\]
DP[i-1][j-1] 确定左上角位置
DP[i-1][j] 确定左下角位置
DP[i, j-1] 确定右上角位置。
根据这三个正方形边长的最小值就可以确定对应位置。
LeetCode——Maximal Square/二维矩阵最大正方形面积

    public int maximalSquare(char[][] matrix) {
        if(matrix==null||matrix.length==0||matrix[0]==null||matrix[0].length==0)
            return 0;
        int row=matrix.length;
        int col=matrix[0].length;
        int max=0;
        //因为矩阵最上面的点是以它自己为一个矩阵的,但是为了计算方便
        //我们假设它有
        int [][] dp=new int[row+1][col+1];
        for(int i=1;i<=row;i++){
            for(int j=1;j<=col;j++){
                if(matrix[i-1][j-1]=='1'){
                  //得到最短的正方形边长
                   dp[i][j]=Math.min(dp[i-1][j],Math.min(dp[i-1][j-1],dp[i][j-1]))+1;
                   max=Math.max(dp[i][j],max); 
                }
            }
        }
        return max*max;
    }
上一篇:torch.where()函数解读


下一篇:30 Day Challenge Day 22 | Leetcode 85. Maximal Rectangle