Java中等题-最大正方形（力扣）

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

这道题首先想到的肯定是暴力法：

 但是我写的暴力解法会超时：

下面是会超时的错误示范：

class Solution {
    public int maximalSquare(char[][] matrix) {
        int n=matrix.length;
        int m=matrix[0].length;
        int X=0;
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                if(matrix[i][j]=='1'){
                    int st=i;
                    int en=j;
                    X=Math.max(1,X);
                    int len=0;
                    while(++st<n&&++en<m&&matrix[++st][++en]=='1'){
                        len++;
                        int st1=st;
                        int en1=en;
                        while((len)>0){
                            if(matrix[st1-len][en1-len]=='0'){
                                continue;
                            }
                            len--;
                        }
                    }
                    X=Math.max(X,(len+1)*2);

                }
            }
        }
        return X;

    }
}

看了官方的解答思路之后，自己写了一遍：动态规划

class Solution {
    public int maximalSquare(char[][] matrix) {
        int n=matrix.length;
        int m=matrix[0].length;
        int dp[][]=new int[n][m];
        int max=0;
        for(int i=0;i<n;i++){
            dp[i][0]=matrix[i][0]-'0';
            if(matrix[i][0]=='1'){
                max=1;
            }
        }
        for(int i=0;i<m;i++){
            dp[0][i]=matrix[0][i]-'0';
            if(matrix[0][i]=='1'){
                max=1;
            }
        }

        for(int i=1;i<n;i++){
            for(int j=1;j<m;j++){
                if(matrix[i][j]=='1'){
                    max=Math.max(1,max);
                    dp[i][j]=Math.min(dp[i-1][j-1],Math.min(dp[i-1][j],dp[i][j-1]))+1;
                    max=Math.max(max,dp[i][j]);
                }else{
                    dp[i][j]=0;
                }
            }
        }

        return max*max;
    }

    public static void main(String[] args) {
        Solution solution=new Solution();
        char s[][]={{'1','0','1','0','0'},{'1','0','1','1','1'},{'1','1','1','1','1'},{'1','0','0','1','0'}};

        int i = solution.maximalSquare(s);
        System.out.println(i);
    }
}

注意：这里的

dp[i][0]=matrix[i][0]-'0';这里至关重要，我就是忽略了这个所以第一次提交的时候有错