Python LeetCode-221. 最大正方形(难度-中等

1.题目描述

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

示例：
输入:
1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0
输出: 4

注意：
输入的1或者0均为字符串类型

2.分析

思路参考这篇文章

• 首先我第一步的想法是这道题目和岛屿的最大面积十分相像，我以为可以采用利用队列进行广度优先查询，但是我发现无法保存什么时候是正方形

• 后来参考了各位大佬的文章，主要是提到了一个思路，那就是构造一个动态规划的列表dp，假定dp[i][j]为一个正方形的右下角，那么判断dp[i][j]他的上边dp[i - 1][j], 左边dp[i][j - 1],左上边 dp[i - 1][j - 1]是否也是1来判断是否能组成一个正方形

• 如果dp[i][j] 对应的其他点每一个点都是2，表示这几个点本身也都对应着一个正方形，所以dp[i][j] 所对应的最大正方形的边长就应该是2+1=3

• 对于最大正方形的边长ans,每次在点dp[i][j] 对应最大边长的时候和ans进行比较，取最大值即可。（也是一个动态规划问题）

• 后面一个算法可以直接在原来的数组上进行记录和修改，更为节约内存

• 做这样的题目就像数学题一样，先找到object之间的关系，再去推演自己想要的算法。

• 位置示意图

3.解决

class Solution:

    def maximalSquare(self, matrix):
        if not matrix or not matrix[0]:
            return 0
        m, n = len(matrix), len(matrix[0])
        dp = [[0] * n for _ in range(m)]
        ans = 0
        for i in range(m):
            for j in range(n):
                dp[i][j] = int(matrix[i][j])
                if i and j and dp[i][j]:
                    dp[i][j] = min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + 1
                ans = max(ans, dp[i][j])
        return ans * ans

• 直接在原数组上进行修改，更为节约内存

class Solution:

    def maximalSquare(self, matrix):
        if not matrix or not matrix[0]:
            return 0
        m, n = len(matrix), len(matrix[0])
        ans = 0
        for i in range(m):
            for j in range(n):
                matrix[i][j] = int(matrix[i][j])
                if i and j and matrix[i][j]:
                    matrix[i][j] = min(matrix[i - 1][j], matrix[i][j - 1], matrix[i - 1][j - 1]) + 1
                ans = max(ans, matrix[i][j])
        return ans * ans