题干
221. 最大正方形
难度中等354收藏分享切换为英文关注反馈
在一个由 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]表示以matrix[i][j]为右下角的最大正方形的边长。
如题干中示例的矩阵，下标索引初始为0，dp[2][3] = 2，因为以matrix[2][3]为右下角的最大正方形边长为2
同理dp[3][4] = 0，因为即使在matrix[3][4] 左上方，有边长为2的正方形，但是这个正方形的右下角并不是matrix[3][4]。
找到了dp数组如何定义，这道题基本就解决了一半了。
具体步骤：
从左到右，从上到下遍历数组，下标为i，j
if matrix[i][j] == 0:
dp[i][j] = 0
if matrix[i][j] == 1:
dp[i][j] = min(dp[i-1][j], dp[i][j-1],dp[i-1][j-1]) + 1
解释一下，如图所示，图中要求点为第四行第四列的元素dp[3][3]
其中红色方框的边长既为dp[3][2], 绿色方框边长为dp[2][3] ，蓝色方框边长为dp[2][2]：
image-20200508160029247.png
由于图中所示的三个方框边长都是3，同时matrix[3][3] = 1 所以dp[3][3] = 3 + 1 = 4
假如三个方框中有一个边长小于3，如图所示
image-20200508160445849.png
则dp[3][3]无论如何也不可能等于4，类似短板原理，这个时候dp[3][3] = min(dp[2][3], dp[3][2],dp[2][2]) + 1 = 3。
所以这样把所有位置的dp值计算出来，取最大值便是最大正方形的边长，要求面积只需要平方即可。
- Tips
- 题目给出的数值为字符串，如
"1"，所以在处理过程中需要进行转换。 - 对于边界的处理，也就是第一行以及第一列的数据，直接令
dp[i][j] = matrix[i][j]即可 - 由于遍历之后matrix原本的数值已经不需要了，所以可以直接把matrix数组当作dp数组，遍历过程中进行修改即可，节省空间
- python代码
class Solution:
def maximalSquare(self, matrix: List[List[str]]) -> int:
if len(matrix) == 0:
return 0
maxlength = 0
for i in range(len(matrix)):
for j in range(len(matrix[0])):
matrix[i][j] = int(matrix[i][j])
if i == 0 or j == 0:
maxlength = max(maxlength, matrix[i][j])
else:
if matrix[i][j] == 1:
matrix[i][j] = min(matrix[i-1][j], min(matrix[i][j-1], matrix[i-1][j-1])) + 1
maxlength = max(maxlength, matrix[i][j])
return maxlength ** 2
