Leetcode 题目解析之 Maximal Square

原创

ruochen

发布于 2022-02-15 15:03:02

1.4K0

发布于 2022-02-15 15:03:02

文章被收录于专栏：若尘的技术专栏

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

For example, given the following matrix:

1 0 1 0 0

1 0 1 1 1

1 1 1 1 1

1 0 0 1 0

Return 4.

动态规划，设dpx是当前matrixx最大的正方形的长。

    public int maximalSquare(char[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return 0;
        }
        int mx = matrix.length;
        int my = matrix[0].length;
        int[][] dp = new int[mx][my];
        int max = 0;
        // 初始化第0行
        for (int i = 0; i < my; i++) {
            if (matrix[0][i] == '1') {
                dp[0][i] = 1;
                max = 1;
            }
        }
        // 初始化第0列
        for (int i = 1; i < mx; i++) {
            if (matrix[i][0] == '1') {
                dp[i][0] = 1;
                max = 1;
            }
        }
        // dp[x][y] = min(dp[x-1][y], dp[x][y-1], dp[x-1][y-1]) + 1
        for (int x = 1; x < mx; x++) {
            for (int y = 1; y < my; y++) {
                if (matrix[x][y] == '1') {
                    dp[x][y] = Math.min(Math.min(dp[x - 1][y], dp[x][y - 1]),
                            dp[x - 1][y - 1]) + 1;
                    max = Math.max(max, dp[x][y]);
                }
            }
        }
        return max * max;
    }

原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。

如有侵权，请联系 cloudcommunity@tencent.com 删除。

area