LeetCode221-最大正方形

发表于 | 分类于

题目链接

英文链接：https://leetcode.com/problems/maximal-square/

中文链接：https://leetcode-cn.com/problems/maximal-square/

题目详述

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

示例:

1
2
3
4
5
6
7
8
输入: 

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

输出: 4

题目详解

动态规划。

  • dp[i][j] 表示右下角处于位置 (i, j) 处的最大正方形的边长。
  • 如果 matrix[i][j] == 0，那么 dp[i][j] = 0。
  • 如果 matrix[i][j] == 1，那么 dp[i][j] = 1 + min{dp[i - 1][j - 1], dp[i][j - 1], dp[i - 1][j]}。
  • 维护一个变量 res，记录每个位置最大正方形的边长，那么最大面积为 res * res。
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
public class LeetCode_00221 {

    public int maximalSquare(char[][] matrix) {
        if (matrix == null || matrix.length == 0) {
            return 0;
        }
        int m = matrix.length, n = matrix[0].length;
        int[][] dp = new int[m][n];
        int res = 0;
        for(int i = 0; i < m; i++){
            dp[i][0] = matrix[i][0] - '0';
            res = Math.max(res, dp[i][0]);
        }
        for(int i = 0; i < n; i++){
            dp[0][i] = matrix[0][i] - '0';
            res = Math.max(res, dp[0][i]);
        }
        for (int i = 1; i < m; ++i) {
            for (int j = 1; j < n; ++j) {
                if (matrix[i][j] == '1') {
                    dp[i][j] = 1 + Math.min(dp[i - 1][j - 1], Math.min(dp[i][j - 1], dp[i - 1][j]));
                    res = Math.max(res, dp[i][j]);
                }
            }
        }
        return res * res;
    }
}

我们可以把上面的 dp 数组在一维和二维上都多开一点空间，统一初始状态的初始化，代码可以写得更简洁。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public class LeetCode_00221 {

    public int maximalSquare(char[][] matrix) {
        if (matrix == null || matrix.length == 0) {
            return 0;
        }
        int m = matrix.length, n = matrix[0].length;
        int[][] dp = new int[m + 1][n + 1];
        int res = 0;
        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (matrix[i - 1][j - 1] == '1') {
                    dp[i][j] = 1 + Math.min(dp[i - 1][j - 1], Math.min(dp[i][j - 1], dp[i - 1][j]));
                    res = Math.max(res, dp[i][j]);
                }
            }
        }
        return res * res;
    }
}
  • 因为 dp[i][j] 只与 dp[i - 1][j - 1]、dp[i][j - 1]、dp[i - 1][j] 这三个状态有关，在数组第一维，当前层只与当前层与上一层的状态的有关，可以将数组第一维大小压缩为 2。
  • 再进一步，我们可以将第一维的大小由 2 压缩置 1。
  • 最终的结果是将二维数组压缩成一维数组，降低空间复杂度。
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
public class LeetCode_00221 {

    public int maximalSquare(char[][] matrix) {
        if (matrix == null || matrix.length == 0) {
            return 0;
        }
        int m = matrix.length, n = matrix[0].length;
        int[] dp = new int[n + 1];
        int pre = 0;
        int res = 0;
        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                int tmp = dp[j];
                if (matrix[i - 1][j - 1] == '1') {
                    dp[j] = 1 + Math.min(pre, Math.min(dp[j - 1], dp[j]));
                    res = Math.max(res, dp[j]);
                } else {
                    dp[j] = 0;
                }
                pre = tmp;
            }
        }
        return res * res;
    }
}