• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

leetcode 221. 最大正方形

开发技术 开发技术 7天前 3次浏览

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

 

示例 1:

leetcode 221. 最大正方形
输入:matrix = [[“1″,”0″,”1″,”0″,”0”],[“1″,”0″,”1″,”1″,”1”],[“1″,”1″,”1″,”1″,”1”],[“1″,”0″,”0″,”1″,”0”]]
输出:4
示例 2:

leetcode 221. 最大正方形
输入:matrix = [[“0″,”1”],[“1″,”0”]]
输出:1
示例 3:

输入:matrix = [[“0”]]
输出:0
 

提示:

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

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/maximal-square
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

 

采用动态规划,每个坐标点的长方形长度都和它的前面三个[(i, j – 1), (i – 1, j), (i – 1, j – 1)]有关系,取最小的 + 1即可。

    public int maximalSquare(char[][] matrix) {
        int x = matrix.length;
        int y = matrix[0].length;

        int[][] arr = new int[x + 1][ y + 1];
        int max = 0;
        for (int i = 0; i < x; i++) {
            for (int j = 0; j < y; j++) {
                if (matrix[i][j] == '1') {
                    arr[i + 1][j + 1] = Math.min(arr[i][j + 1], Math.min(arr[i + 1][j],arr[i][j])) + 1;
                    max = Math.max(max, arr[i + 1][j + 1]);
                }
            }
        }
        return max * max;
    }

leetcode 221. 最大正方形


程序员灯塔
转载请注明原文链接:leetcode 221. 最大正方形
喜欢 (0)