221. Maximal Square

一、题目

　　1、审题

　　2、分析

　　　　求出只包含字符 0 、 1 的二维矩阵中的 1 形成的最大正方形的面积

二、解答

　　1、思路：

　　　　方法一、

　　　　　　动态规划，采用二维数组 dp[][]，dp[i][j] 表示在位置 [i][j] 作为右下角顶点所形成的正方形的最大边长。

　　　　　　动态规划方程为：

　　　　　　　　if(matrix[i][j] == '0') dp[i][j] = 0;

　　　　　　　　if(matrix[i][j] == '1') dp[i][j] = Min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1;

 1     public int maximalSquare(char[][] matrix) {
 2      
 3         if(matrix == null)
 4             return 0;
 5         int rows = matrix.length;
 6         if(rows == 0)
 7             return 0;
 8         int cols = matrix[0].length;
 9         int[][] dp = new int[rows][cols];
10         int size = 0;
11         
12         for (int i = 0; i < rows; i++) {
13             dp[i][0] = matrix[i][0] - '0';
14             size = Math.max(size, dp[i][0]);
15         }
16         
17         for (int i = 0; i < cols; i++) {
18             dp[0][i] = matrix[0][i] - '0';
19             size = Math.max(size, dp[0][i]);
20         }
21         
22         for (int row = 1; row < rows; row++) {
23             for (int col = 1; col < cols; col++) {
24                 if(matrix[row][col] == '1') {
25                     dp[row][col] = Math.min(dp[row-1][col-1], Math.min(dp[row-1][col], dp[row][col-1])) + 1;
26                     size = Math.max(size, dp[row][col]);
27                 }
28             }
29         }
30         
31         return size * size;
32     }

　　优化：可以采用两个一维数组，记录当前行与上一行即可。

　　注意：数组，cur、pre，不可采用 pre = cur 进行赋值，因为此时 pre 会随着 cur 一同修改值，因为指向了同一地址。

 1     public int maximalSquare2(char[][] matrix) {
 2         
 3         if(matrix == null)
 4             return 0;
 5         
 6         int rows = matrix.length;
 7         if(rows == 0)
 8             return 0;
 9         int cols = matrix[0].length;
10         int size = 0;
11         // 只记录两行的取值
12         int[] pre = new int[cols];
13         int[] cur = new int[cols];
14         for (int i = 0; i < cols; i++) {
15             pre[i] = matrix[0][i] - '0';
16             size = Math.max(size, pre[i]);
17         }
18         
19         for (int row = 1; row < rows; row++) {
20             cur[0] = matrix[row][0] - '0';
21             size = Math.max(size, cur[0]);
22             for (int col = 1; col < cols; col++) {
23                 if(matrix[row][col] == '1') {
24                     cur[col] = Math.min(cur[col - 1], Math.min(pre[col - 1], pre[col])) + 1; 
25                     size = Math.max(size, cur[col]);
26                 }
27                 else {
28                     cur[col] = 0;
29                 }
30             }
31             // pre = cur;   错误，pre会随 cur 一同更改
32             pre = Arrays.copyOf(cur, cur.length);
33         }
34         return size * size;
35     }

　　优化：

　　　　可以采用一个数组记录当前行的最大正方形边长，

　　　　另加一个变量记录上一行的 [i-1][j-1] 的值。

 1     public int maximalSquare3(char[][] matrix) {
 2         
 3         if(matrix == null)
 4             return 0;
 5         
 6         int rows = matrix.length;
 7         if(rows == 0)
 8             return 0;
 9         int cols = matrix[0].length;
10         // 只记录一行的取值, cols + 1, 效果如同 在 matrix 左边加了一列 值为 0 的列。
11         int[] dp = new int[cols + 1];
12         int size = 0, pre = 0; // pre 指向[i-1][j-1] 的位置
13         for (int row = 0; row < rows; row++) {
14             for (int col = 1; col <= cols; col++) {
15                 int tmp = dp[col];
16                 if(matrix[row][col-1] == '1') {
17                     dp[col] = Math.min(dp[col], Math.min(dp[col-1], pre)) + 1;
18                     size = Math.max(size, dp[col]);
19                 }
20                 else {
21                     dp[col] = 0;
22                 }
23                 pre = tmp;
24             }
25         }
26         return size * size;
27     }