LeetCode.221.Maximal Square 最大正方形

题目描述

221 Maximal Square
https://leetcode-cn.com/problems/maximal-square/

Given a 2D binary matrix filled with 0’s and 1’s, find the largest square containing only 1’s and return its area.

Example:

Input:

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

Output: 4

---

相似题目

LeetCode.221.Maximal Square 最大正方形

1277 统计全为 1 的正方形子矩阵
https://leetcode-cn.com/problems/count-square-submatrices-with-all-ones/

---

解题过程

BFS暴力搜索

我只会暴力搜索方法，每次遇到 1 ，把他当做正方形的左上角坐标，开始向 右下方做 BFS 广度优先搜索
搜索过程中用 edge 记录正方形边长， 每一层值全为 1 时则边长 edge 加1，否则结束。
则以所有 1 为左上角的正方形中边长最大的就是结果，返回 edge^2 即可。

这个方法复杂度比较高，因为我们做了大量重复搜索，时间复杂度 O(m^2n^2)，空间复杂度 O(mn)

private static class SolutionV2020 {
    int[] dx = { 1, 1, 0};
    int[] dy = { 0, 1, 1};
    int rows, columns;
    public int maximalSquare(char[][] matrix) {
        if (matrix == null || matrix.length == 0) {
            return 0;
        }
        rows = matrix.length;
        columns = matrix[0].length;

        int maxEdge = 0;
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < columns; j++) {
                if (matrix[i][j] == '1') {
                    int edge = bfs(matrix, i, j);
                    maxEdge = Math.max(maxEdge, edge);
                }
            }
        }
        return maxEdge * maxEdge;
    }

    // 从 (x,y) 开始一次BFS，并返回全为1的最大正方形边长
    private int bfs(char[][] matrix, int x, int y) {
        int edge = 1;
        Set<int[]> visited = new HashSet<>();
        Queue<int[]> queue = new LinkedList<>();
        visited.add(new int[] {x, y});
        queue.offer(new int[] {x, y});

        while (!queue.isEmpty()) {
            int levelCount = queue.size();
            for (int i = 0; i < levelCount; i++) {
                int[] cur = queue.poll();
                for (int k = 0; k < 3; k++) {
                    int xx = cur[0] + dx[k], yy = cur[1] + dy[k];
                    if (xx < rows && yy < columns && matrix[xx][yy] == '1') {
                        visited.add(new int[] {xx, yy});
                        queue.offer(new int[] {xx, yy});
                    } else {
                        return edge;
                    }
                }
            }
            edge++;
        }
        return edge;
    }
}

动态规划

设 dp[i, j] 表示以 (i,j) 为右下角的全 1 正方形的最大边长，则
当 matrix[i][j] == 0 时，dp[i, j] = 0
否则有递推公式
dp[i, j] = min(dp[i-1, j-1], dp[i-1, j], dp[i, j-1]) + 1
找个具体的例子就比较好理解，

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

上图中，对于以 (3,3) 为右下角的正方形，由于其左边是 0， 即 dp[i, j-1] 是 0，所以 dp[3][3] 只能是1，形象化理解是：由 1 组成的正方形没连接上

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

上图中，对于以 (3,3) 为右下角的正方形，由于其 左、左上、上 侧的 dp 值都是2，所以 dp[3][3] 值为 3，形象化理解是：只有当其 左、左上、上 三个方向的全1正方形能连起来时，可取其中最小的加1

---

GitHub代码

algorithms/leetcode/leetcode/_221_MaximalSquare.java
https://github.com/masikkk/algorithms/blob/master/leetcode/leetcode/_221_MaximalSquare.java

---