LeetCode 221 Maximal Square

LeetCode

Given an m x n binary matrix filled with 0‘s and 1‘s, find the largest square containing only 1‘s and return its area.

Example 1:

Input: matrix = [[“1”,”0”,”1”,”0”,”0”],[“1”,”0”,”1”,”1”,”1”],[“1”,”1”,”1”,”1”,”1”],[“1”,”0”,”0”,”1”,”0”]]
Output: 4

Example 2:

Input: matrix = [[“0”,”1”],[“1”,”0”]]
Output: 1

Example 3:

Input: matrix = [[“0”]]
Output: 0

Constraints:

m == matrix.length n == matrix[i].length
1 <= m, n <= 300 matrix[i][j] is '0' or '1'.

题目大意：

求子正方形矩阵全是1的最大面积

解题思路：

求最值且是矩阵考虑用DP，但公式比较难写。
dp[i][j]为以(i-1, j-1)为右下端点的正方形的边长
递归式：

1 2	dp[i][j] = min{dp[i-1][j-1], dp[i-1][j], dp[i][j-1]} + 1 if matrix[i][j] == 1 = 0 otherwise

解题步骤：

严格遵守DP的5点注意事项

注意事项：

严格遵守DP的5点注意事项。初始值是0，表示第一行或第一列的点的边长最多只能为1.
输入是字符，所以比较是否1时候用字符比较

Python代码：

# dp[i][j] = min{dp[i-1][j-1], dp[i-1][j], dp[i][j-1]} + 1 if matrix[i][j] == 1
#          = 0                                             otherwise
def maximalSquare(self, matrix: List[List[str]]) -> int:
	dp = [[0 for _ in range(len(matrix[0]) + 1)] for _ in range(len(matrix) + 1)] # remember 0 not 1 or float(inf)
	# dp[0][0] = 0
	res = 0
	for i in range(1, len(dp)):
		for j in range(1, len(dp[0])):
			dp[i][j] = min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + 1 if matrix[i - 1][j - 1] == '1' else 0 # remember '1' not 1
			res = max(res, dp[i][j])
	return res * res

算法分析：

时间复杂度为O(n²)，空间复杂度O(n²)