LeetCode刷题笔记：字节跳动-动态或贪心(2)-最大正方形

3.最大正方形

在一个由 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矩阵，dp[i][j]代表以(i,j)为右下角的最大正方形的边长。初始时设置dp[i][0]和dp[0][j]为matrix[i][0]与matrix[0][j],然后dp[i][j]的值即为dp[i-1][j],dp[i][j-1],dp[i-1][j-1]三者间的最小值+1,最后输出最大边长的平方即可，代码如下：

class Solution(object):
    def maximalSquare(self, matrix):
        """
        :type matrix: List[List[str]]
        :rtype: int
        """
        if matrix==[]:
            return 0
        m,n = len(matrix),len(matrix[0])
        dp = [[0 for x in range(n)] for x in range(m)]
        mx = 0
        for i in range(n):
            dp[0][i]=int(matrix[0][i])
            mx = max(dp[0][i],mx)
        for i in range(m):
            dp[i][0]=int(matrix[i][0])
            mx = max(dp[i][0],mx)
        for i in range(1,m):
            for j in range(1,n):
                if matrix[i][j]=='0':
                    continue
                dp[i][j]=min(dp[i-1][j],dp[i][j-1],dp[i-1][j-1])+1
                mx = max(mx,dp[i][j])
        return mx**2