最大正方形

题目描述：

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

思路：

动态规划：

d[] []用来存储以坐标为i,j的元素为正方形最右下角那一格所构成的正方形的最大边长

若matrix[i] [j]为0，d[i] [j]明显也为0

结合图形动手画一下就会发现，如果d[i-1] [j-1],d[i-1] [j] ,d[i] [j-1]三者相等时且matrix[i] [j]刚好为1时，原来的正方形就会往外扩展一格，即边长加一，如果这三个值不相等，那么d[] []就等于三者最小值加一

最后返回d中最大值的平方即可。

代码：

public static int maximalSquare(char[][] matrix) {
    int max = 0;
    int[][] d = new int[matrix.length][matrix[0].length];
    for (int i = 0; i < matrix.length; i++) {
        for (int j = 0; j < matrix[0].length; j++) {
            if(i==0){
                d[i][j] = matrix[0][j]=='1'?1:0;
                max = Math.max(max,d[i][j]);
                continue;
            }
            if(j==0){
                d[i][j]=matrix[i][j]=='1'?1:0;
                max = Math.max(max,d[i][j]);
                continue;
            }
            if(matrix[i][j]==0){
                d[i][j]=0;
                continue;
            }
            if(d[i-1][j-1]==d[i-1][j]&&d[i-1][j-1]==d[i][j-1]){
                d[i][j] = d[i-1][j-1]+1;
            }
            else{
                d[i][j] = Math.min(Math.min(d[i-1][j-1],d[i][j-1]),d[i-1][j])+1;
            }
            max = Math.max(max,d[i][j]);
        }
    }

    return max*max;

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32