LeetCode如何實(shí)現(xiàn)最大正方形

發(fā)布時(shí)間：2021-12-15 10:54:14 來(lái)源：億速云閱讀：160 作者：小新欄目：大數(shù)據(jù)

這篇文章將為大家詳細(xì)講解有關(guān)LeetCode如何實(shí)現(xiàn)最大正方形，小編覺得挺實(shí)用的，因此分享給大家做個(gè)參考，希望大家閱讀完這篇文章后可以有所收獲。

題目描述

0 和 1 組成一個(gè)字符型二維矩陣，在其中找到只包含 1 的最大正方形，并返回其面積。如：輸入

[["1","0","1","0","0"],

["1","0","1","1","1"],

["1","1","1","1","1"],

["1","0","0","1","0"]]

返回4。

題解

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

在LeetCode刷題DAY 2：最長(zhǎng)回文子串中我們介紹了動(dòng)態(tài)規(guī)劃的含義，本次不再贅述，直接進(jìn)入邏輯闡述。

第一步，找到中間狀態(tài)：此處中間狀態(tài)st[i][j]表示以矩陣中(i，j)元素作為正方形右下角頂點(diǎn)，可以得到最大正方形邊長(zhǎng)。
第二步，確定狀態(tài)轉(zhuǎn)移：如果(i，j)為0，則當(dāng)前位置狀態(tài)值為0，否則狀態(tài)值取決于其上面、左面和左上角狀態(tài)值，轉(zhuǎn)移關(guān)系為st[i][j]=min(st[ist[i][j]=min(st[i-1][j],st[i-1][j-1],st[i][j-1])+1，即周圍最小狀態(tài)值+1。不理解的可以找個(gè)案例手動(dòng)算一下。且要注意的是，如果該元素在整個(gè)矩陣的最外邊，則狀態(tài)值僅根據(jù)該元素取值判斷即可。

class Solution:    def maximalSquare(self, matrix: List[List[str]]) -> int:        if len(matrix)==0:            return 0        # len(matrix)得到的是矩陣行數(shù)        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

關(guān)于“LeetCode如何實(shí)現(xiàn)最大正方形”這篇文章就分享到這里了，希望以上內(nèi)容可以對(duì)大家有一定的幫助，使各位可以學(xué)到更多知識(shí)，如果覺得文章不錯(cuò)，請(qǐng)把它分享出去讓更多的人看到。

向AI問一下細(xì)節(jié)

LeetCode如何實(shí)現(xiàn)最大正方形

猜你喜歡

最新資訊

相關(guān)推薦

相關(guān)標(biāo)簽