溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
這篇文章將為大家詳細講解有關LeetCode如何實現最大正方形，小編覺得挺實用的，因此分享給大家做個參考，希望大家閱讀完這篇文章后可以有所收獲。
1
題目描述
0 和 1 組成一個字符型二維矩陣，在其中找到只包含 1 的最大正方形，并返回其面積。如：輸入
[["1","0","1","0","0"],
["1","0","1","1","1"],
["1","1","1","1","1"],
["1","0","0","1","0"]]
返回4。
2
題解
第一步，找到中間狀態：此處中間狀態st[i][j]表示以矩陣中(i，j)元素作為正方形右下角頂點，可以得到最大正方形邊長。
第二步，確定狀態轉移：如果(i，j)為0，則當前位置狀態值為0，否則狀態值取決于其上面、左面和左上角狀態值，轉移關系為st[i][j]=min(st[ist[i][j]=min(st[i-1][j],st[i-1][j-1],st[i][j-1])+1，即周圍最小狀態值+1。不理解的可以找個案例手動算一下。且要注意的是，如果該元素在整個矩陣的最外邊，則狀態值僅根據該元素取值判斷即可。
class Solution: def maximalSquare(self, matrix: List[List[str]]) -> int: if len(matrix)==0: return 0 # len(matrix)得到的是矩陣行數 st = [[0]*len(matrix[0]) for _ in range(len(matrix))] maxlong = [] for i in range(len(matrix)): for j in range(len(matrix[0])): if matrix[i][j]=='1': if i*j==0: st[i][j]=1 else: st[i][j]=min(st[i-1][j],st[i-1][j-1],st[i][j-1])+1 maxlong.append(max(st[i])) return max(maxlong)**2
關于“LeetCode如何實現最大正方形”這篇文章就分享到這里了，希望以上內容可以對大家有一定的幫助，使各位可以學到更多知識，如果覺得文章不錯，請把它分享出去讓更多的人看到。
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
