221. Maximal Square(Medium)
这道题剑指offer上也有,比较巧妙,暴力方法需要O(n*k),而双向队列缩短到了O(n)
在一个由 0 和 1 组成的二维矩阵内,找到只包含 1 的最大正方形,并返回其面积。
Example:
Input:
1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0
Output: 4
不得不说这道题非常巧妙,把每个矩形的问题转换成了二维数组每个数与其正上、正左、左上三个坐标之间的关系,dp(i,j)表示点(i,j)为终点的最大正方形。转移方程式如下:
dp(i,j)=min(dp(i−1,j),dp(i−1,j−1),dp(i,j−1))+1.
image.png
def maximalSquare(self, matrix):
"""
:type matrix: List[List[str]]
:rtype: int
"""
if not matrix or not matrix[0]:
return 0
row = len(matrix)
column = len(matrix[0])
Max = 0
dp = [[0 for j in range(column)] for i in range(row)]
for i in range(0, row):
for j in range(0, column):
if i == 0 or j == 0:
dp[i][j] = int(matrix[i][j])
elif matrix[i][j] == '1':
dp[i][j] = min(dp[i-1][j],dp[i][j-1],dp[i-1][j-1]) + 1
else:
dp[i][j] = 0
Max = max(Max,dp[i][j])
return Max**2
还可以再优化,DP每个点的位置只与三个点有关。
def maximalSquare(self, matrix):
"""
:type matrix: List[List[str]]
:rtype: int
"""
if not matrix or not matrix[0]:
return 0
row = len(matrix)
column = len(matrix[0])
dp = [0]*(column + 1)
maxlen = prev = 0
for i in range(1, row+1):
for j in range(1, column+1):
temp = dp[j]
if matrix[i-1][j-1] == '1':
dp[j] = min(dp[j-1], dp[j], prev) + 1
else:
dp[j] = 0
maxlen = max(maxlen,dp[j])
prev = temp
return maxlen**2
网友评论