#221 最大正方形
题目描述
在一个由 '0'
和 '1'
组成的二维矩阵内,找到只包含 '1'
的最大正方形,并返回其面积。
示例 1:
输入:matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
输出:4
题目解释
如果想让右下角为正方形的右下角,必须红、绿、蓝、三个框框内所有元素都为1。
进一步思考
右下角为正方形的右下角的边长,是三个框框中最小的那个+1。因为三个框框分别对应了。正方形其余是几条边。因为木桶效应,新的正方形边长当然是最短的边+1了。
定义dp[i][j]dp[i][j]dp[i][j]是以i,ji,ji,j为正方形右下角的最大正方形边长。图中红色框框的边长dp[i−1][j−1]dp[i-1][j-1]dp[i−1][j−1],绿色的边长dp[i][j−1]dp[i][j-1]dp[i][j−1],蓝色的边长dp[i−1][j]dp[i-1][j]dp[i−1][j]。那么推导公式。
mat[i][j]=0−>dp[i][j]=0mat[i][j]=1−>min(dp[i−1][j−1],dp[i−1][j],dp[i][j−1])+1mat[i][j]=0->dp[i][j]=0\\ mat[i][j]=1->min(dp[i-1][j-1],dp[i-1][j],dp[i][j-1])+1 mat[i][j]=0−>dp[i][j]=0mat[i][j]=1−>min(dp[i−1][j−1],dp[i−1][j],dp[i][j−1])+1
初始化
根据推导公式和定义初始化,应该初始化第0行和第0列。初始化值应该与矩阵中的值对应。
代码
class Solution:def maximalSquare(self, matrix: List[List[str]]) -> int:"""定义dp[i][j]以i,j为右下角的最大正方形面积边长"""m=len(matrix)n=len(matrix[0])dp=[[0 for _ in range(n)] for _ in range(m)]for i in range(m):if matrix[i][0]=='1':dp[i][0]=1for j in range(n):if matrix[0][j]=='1':dp[0][j]=1for i in range(1,m):for j in range(1,n):if matrix[i][j]=='1':dp[i][j]=min(dp[i-1][j-1],dp[i-1][j],dp[i][j-1])+1else:dp[i][j]=0max_len=0for i in range(m):for j in range(n):max_len=max(max_len,dp[i][j])return max_len**2