221. 最大正方形

題目

在一個由 0 和 1 組成的二維矩陣內(nèi)，找到只包含 1 的最大正方形，并返回其面積。

示例:

輸入:

1 0 1 0 0

1 0 1 1 1

1 1 1 1 1

1 0 0 1 0

輸出: 4

解題思路

思路：動態(tài)規(guī)劃

本篇幅使用動態(tài)規(guī)劃的原理來解決該問題。我們用 dp(i, j) 表示以 (i, j) 為右下角，且只包含 1 的正方形的邊長最大值。如果能夠求出所有的 dp(i, j) 值，其中最大值就是最大正方形的邊長，其平方就是我們要求的面積。

根據(jù)題意要求，所給的二維矩陣內(nèi)，只有包含 1 的才能構(gòu)造正方形。如果 dp(i, j) =為 0 的情況下，討論是否能夠構(gòu)成正方形并求出最長邊就沒有意義，因為這位置不能在構(gòu)成由 1 組成的正方形中。

那么如果該位置為 1 的情況下，就需要考慮三個位置的情況，如下圖：

先看下構(gòu)成正方形的情況，結(jié)合上面的圖示，如果當(dāng)前的值為 1，那么要找出最長的邊，就需要考慮從當(dāng)前位置出發(fā)，上面，左邊，左上的值都必須是 1，只有這樣，再加上當(dāng)前位置才有可能構(gòu)成正方形。

也就是說，這三個方向都不能是 0。但是如果當(dāng)前位置為 1，但三個方向受限制的情況下，三個方向的邊不一定都一樣，那么構(gòu)成的正方形的邊長則需要取三者最短邊，再加 1，表示加上當(dāng)前的位置。

具體如上示圖，上面的數(shù)字表示以此為正方形右下角的最大邊長，其中 ？ 表示作為右下角的正方形區(qū)域。

其中左圖，受左上角 0 的限制，這里可構(gòu)成的正方形的最長邊為 3。

中間的圖例中，受上邊 0 的限制，這里可構(gòu)成的正方形的最長邊為 2。

最后的圖例中，受左邊 0 的限制，這里可構(gòu)成的正方形的最長邊為 2。

可以看出，得出的最長邊都是上，左，左上三個正方形中最小邊長 + 1。

所以狀態(tài)轉(zhuǎn)移方程為：

dp(i, j) = min(dp(i-1, j), dp(i-1, j-1), dp(i, j-1)) + 1

那么具體的代碼實現(xiàn)如下。

代碼實現(xiàn)

class Solution:

def maximalSquare(self, matrix: List[List[str]]) -> int:

if len(matrix) == 0:

return 0

rows = len(matrix)

cols = len(matrix[0])

max_side = 0

dp = [[0] * cols for _ in range(rows)]

for i in range(rows):

for j in range(cols):

# 當(dāng)前的值為 1 時，考慮求構(gòu)成正方形的最長邊

if matrix[i][j] == '1':

# 當(dāng)前值為 1，處于首行首列時，不考慮左，上，左上三個方向

if i == 0 or j == 0:

dp[i][j] = 1

else:

dp[i][j] = min(dp[i-1][j], dp[i-1][j-1], dp[i][j-1]) + 1

max_side = max(max_side, dp[i][j])

square = max_side ** 2

return square

實現(xiàn)效果

以上就是使用動態(tài)規(guī)劃，找出最長邊，進而解決《221. 最大正方形》問題的主要內(nèi)容。

歡迎關(guān)注微信公眾號《書所集錄》

總結(jié)

以上是生活随笔為你收集整理的python最大正方形的面积_LeetCode 221. 最大正方形 | Python的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。