leetcode221-最大正方形

原题

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

示例:

输入: 

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

输出: 4

解法

思想

动态规划:

dp(x,y)是以matrix[x][y]为右下角的点的最大正方形的边长,则如果matrix[x][y]=='1',那么dp(x,y)=min(dp(x-1,y-1),dp(x-1,y),dp(x,y-1))。否则dp(x,y)=0

代码

class Solution {

    public int maximalSquare(char[][] matrix) {
        int height = matrix.length;
        if(height == 0) return 0;
        int width = matrix[0].length;
        int[][] edge = new int[height][width];
        int maxEdge = 0;
        for(int i = 0 ; i < height;i++){
            for(int j = 0;j < width;j++){
                if(matrix[i][j] == '0'){
                    edge[i][j] = 0;
                    continue;
                }
                int leftUp = (i == 0 || j == 0) ? 0 : edge[i-1][j-1];
                int left = j == 0 ? 0 : edge[i][j-1];
                int up = i == 0 ? 0 : edge[i-1][j];
                edge[i][j] = Math.min(Math.min(leftUp,left),up) +1;
                if(edge[i][j]>maxEdge) maxEdge = edge[i][j];
            }
        }
        return maxEdge*maxEdge;
    }
}

原创文章,作者:彭晨涛,如若转载,请注明出处:https://www.codetool.top/article/leetcode221-%e6%9c%80%e5%a4%a7%e6%ad%a3%e6%96%b9%e5%bd%a2/

发表评论

电子邮件地址不会被公开。