Jianbo Dai's

lc221.最大正方形

 
  • Mar 26, 2021

题目链接

这个题是华为面试的时候给我出的，我就直接用bfs做出来了，当然那样做时间复杂度比较高为O(mn min(m,n)^2)，空间复杂度为O（1）。就不多说了。讲一下动态规划怎么做，首先我们用dp(i, j)表示以(i, j)为右下角，且只包含1的正方形的边长的最大值。如果我们能计算出所有dp(i, j)的值，那么其中的最大值即为矩阵中只包含1的正方形的边长的最大值，其平方为最大正方形的面积。那么如何计算dp中每个元素呢？对于每个位置(i, j)，检查在矩阵中该位置的值：如果该位置的值是0，则dp(i, j)=0，因为当前位置不可能在由1组成的正方形中。如果该位置的值是1，则dp(i, j)的值由其上方，左方和左上方的三个相邻位置的dp值决定。具体而言，当前位置的元素值大于三个相邻位置的元素中的最小值加1，状态转移方程为: dp(i, j) = min(dp(i-1, j), dp(i, j-1), dp(i-1, j-1)) + 1 证明见lc1277的相关题解。另外还需要考虑边界条件，如果i和j中至少有一个为0，则以位置(i, j)为右下角的最大正方形的边长只能是1，因此dp(i, j) = 1。这样的话算法的时间复杂度是O（MN），空间复杂度是O（MN）。

python:

class Solution:
    def maximalSquare(self, matrix: List[List[str]]) -> int:
        if not matrix:
            return 0
        row, col = len(matrix), len(matrix[0])
        dp = [[0]*col for _ in range(row)]
        maxSide = 0
        for x in range(row):
            for y in range(col):
                if matrix[x][y] == "1":
                    if x == 0 or y == 0:
                        dp[x][y] = 1
                    else:
                        dp[x][y] = min(dp[x-1][y], dp[x][y-1], dp[x-1][y-1]) + 1
                    maxSide = max(dp[x][y], maxSide)
        
        maxArea = maxSide * maxSide
        return maxArea
Search