LeetCode 221 Maximal Square

LeetCode

<div>

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:

<pre>Input: matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]] Output: 4 </pre>

Example 2:

<pre>Input: matrix = [["0","1"],["1","0"]] Output: 1 </pre>

Example 3:

<pre>Input: matrix = [["0"]] Output: 0 </pre>

Constraints:

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

</div>

题目大意：

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

解题思路：

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

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点注意事项

注意事项：

1. 严格遵守DP的5点注意事项。初始值是0，表示第一行或第一列的点的边长最多只能为1.
2. 输入是字符，所以比较是否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

算法分析：

时间复杂度为<code>O(n²)</code>，空间复杂度<code>O(n²)</code>