221. 最大正方形

题目描述:  

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

  示例:

  输入:

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

  输出: 4

题解:

 dp(i,j) 表示的是由 1 组成的最大正方形的边长;

  dp(i, j)=min(dp(i1, j), dp(i1, j1), dp(i, j1))+1

public class L221 {
    public int maximalSquare(char[][] matrix) {
        if(matrix.length == 0 ||(matrix.length==1 &&matrix[0].length==0)){return 0;}
        int[][] resLen = new int[matrix.length][matrix[0].length];
        int maxLen = 0;
        for (int i = 0;i<matrix.length;i++){
            if(matrix[i][0] == '1'){maxLen = 1;}
            resLen[i][0] = Integer.parseInt(String.valueOf(matrix[i][0]));
        }
        for (int j = 0;j < matrix[0].length;j++){
            if(matrix[0][j] == '1'){maxLen = 1;}
            resLen[0][j] = Integer.parseInt(String.valueOf(matrix[0][j]));
        }
        for (int i = 1;i<matrix.length;i++){
            for (int j= 1;j < matrix[0].length;j++){
                int re = 0;
                if(matrix[i][j] == '1'){
                    re = Math.min(resLen[i-1][j-1],Math.min(resLen[i-1][j],resLen[i][j-1])) +1 ;
                    maxLen = Math.max(re,maxLen);
                }
                resLen[i][j] = re;
            }
        }
        return maxLen * maxLen;
    }
}
原文地址:https://www.cnblogs.com/mayang2465/p/12021822.html