当前位置 : 首页 » 文章分类 :  算法  »  LeetCode.221.Maximal Square 最大正方形

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


上一篇 LeetCode.069.Sqrt(x) x的平方根

下一篇 LeetCode.983.Minimum Cost For Tickets 最低票价

阅读
评论
727
阅读预计3分钟
创建日期 2020-05-08
修改日期 2020-05-08
类别

页面信息

location:
protocol:
host:
hostname:
origin:
pathname:
href:
document:
referrer:
navigator:
platform:
userAgent:

评论