美文网首页
[Leetcode] 221. 最大正方形

[Leetcode] 221. 最大正方形

作者: 丶噗噗噗噗噗 | 来源:发表于2020-05-08 10:05 被阅读0次

221. 最大正方形

来源: 221. 最大正方形

1. 题目描述

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

2. 解题思路

动态规划,dp[i][j]=min(dp[i-1][j-1],dp[i-1][j],dp[i][j-1])+1

3. 代码

class Solution:
    def maximalSquare(self, matrix: List[List[str]]) -> int:
        if(not matrix):
            return 0
        m=len(matrix)
        n=len(matrix[0])
        res=0
        dp=[[0]*(n+1) for _ in range(m+1)]
        for i in range(1,m+1):
            for j in range(1,n+1):
                if(matrix[i-1][j-1]=="1"):
                    dp[i][j]=min(dp[i-1][j-1],dp[i-1][j],dp[i][j-1])+1
                    res=max(dp[i][j],res)
        return res*res


# 参考:wu_yan_zu
# 链接:https://leetcode-cn.com/problems/maximal-square/solution/dong-tai-gui-hua-kong-jian-you-hua-zhu-xing-jie-2/

相关文章

网友评论

      本文标题:[Leetcode] 221. 最大正方形

      本文链接:https://www.haomeiwen.com/subject/xvmxnhtx.html