221. 最大正方形(中等)

Posted on Edited on In Views:

1，问题描述

221. 最大正方形

难度：中等

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

示例 1：

img

1
2
输入：matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
输出：4

示例 2：

img

1
2
输入：matrix = [["0","1"],["1","0"]]
输出：1

示例 3：

1
2
输入：matrix = [["0"]]
输出：0

提示：

  • m == matrix.length
  • n == matrix[i].length
  • 1 <= m, n <= 300
  • matrix[i][j] 为 '0' 或 '1'

2，初步思考

​ 直接使用动态规划处理

​ 动态方程：

​ dp【i】【j】=Math.min（i，j坐标的连续长度为1的行、列最小值，dp【i】【j】+1）

3，代码处理

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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
public class _221最大正方形 {

    // 动态规划处理:优化重复计算
    // 时间复杂度：O(n*m)，空间复杂度：O(n*m)
    public int maximalSquare_dp_option(char[][] matrix) {
        n = matrix.length;
        m = matrix[0].length;
        int maxLen = 0;
        int[][] dp = new int[n + 1][m + 1];
        int[][] dpUpdown = new int[n + 1][m + 1];
        int[][] dpLeftRight = new int[n + 1][m + 1];
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {// 检测2个边界的最短边长
                if (matrix[i - 1][j - 1] == '0') {
                    dpUpdown[i][j] = 0;
                    dpLeftRight[i][j] = 0;
                    dp[i][j] = 0;
                } else {
                    dpUpdown[i][j] = dpUpdown[i][j - 1] + 1;
                    dpLeftRight[i][j] = dpLeftRight[i - 1][j] + 1;
                    dp[i][j] = Math.min(Math.min(dpLeftRight[i][j], dpUpdown[i][j]), dp[i - 1][j - 1] + 1);
                    maxLen = Math.max(dp[i][j], maxLen);
                }
            }
        }
        return maxLen * maxLen;
    }

    // 动态规划处理
    public int maximalSquare_dp(char[][] matrix) {
        n = matrix.length;
        m = matrix[0].length;
        int maxLen = 0;
        int[][] dp = new int[n + 1][m + 1];
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                // 检测2个边界的最短边长
                int maxLenCur = 0;
                for (int k = 0; k < dp[i - 1][j - 1] + 1; k++) {
                    if (matrix[i - k - 1][j - 1] == '1' && matrix[i - 1][j - k - 1] == '1') {
                        maxLenCur++;
                    } else {
                        break;
                    }
                }
                dp[i][j] = maxLenCur;
                maxLen = Math.max(maxLenCur, maxLen);
            }
        }
        return maxLen * maxLen;
    }

    int n, m, maxLen;

    // 广度有限搜索，暴力求解
    public int maximalSquare(char[][] matrix) {
        n = matrix.length;
        m = matrix[0].length;
        maxLen = 0;
        for (int i = 0; i < n - maxLen; i++) {
            for (int j = 0; j < m - maxLen; j++) {
                int bfs = bfs(matrix, i, j);
                System.out.println("i:" + i + " ,j:" + j + " ,len:" + bfs);
                maxLen = Math.max(bfs, maxLen);
            }
        }
        return maxLen * maxLen;
    }

    private int bfs(char[][] matrix, int i, int j) {
        for (int len = 0; true; len++) {// 长度
            if (i + len >= n || j + len >= m) return len;// 超出边界
            for (int idx = 0; idx <= len; idx++) {
                if (matrix[i + len][j + idx] == '0' || matrix[i + idx][j + len] == '0') return len;
            }
        }
    }

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

        char[][] matrix = new char[][]{
                {'1', '1', '0', '1'},
                {'1', '1', '0', '1'},
                {'1', '1', '1', '1'}};

//        char[][] matrix = new char[][]{{'0', '1'}, {'1', '0'}};

        _221最大正方形 obj = new _221最大正方形();
        System.out.println(obj.maximalSquare_dp_option(matrix));
    }
}