1.題目描述

在一個由 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

注意：
輸入的1或者0均為字符串類型

2.分析

思路參考這篇文章

• 首先我第一步的想法是這道題目和島嶼的最大面積十分相像，我以為可以采用利用隊(duì)列進(jìn)行廣度優(yōu)先查詢次洼，但是我發(fā)現(xiàn)無法保存什么時候是正方形

• 后來參考了各位大佬的文章，主要是提到了一個思路遇骑，那就是構(gòu)造一個動態(tài)規(guī)劃的列表dp卖毁，假定dp[i][j]為一個正方形的右下角，那么判斷dp[i][j]他的上邊dp[i - 1][j], 左邊dp[i][j - 1],左上邊 dp[i - 1][j - 1]是否也是1來判斷是否能組成一個正方形

• 如果dp[i][j] 對應(yīng)的其他點(diǎn)每一個點(diǎn)都是2落萎，表示這幾個點(diǎn)本身也都對應(yīng)著一個正方形亥啦，所以dp[i][j] 所對應(yīng)的最大正方形的邊長就應(yīng)該是2+1=3

• 對于最大正方形的邊長ans,每次在點(diǎn)dp[i][j] 對應(yīng)最大邊長的時候和ans進(jìn)行比較炭剪，取最大值即可。（也是一個動態(tài)規(guī)劃問題）

• 后面一個算法可以直接在原來的數(shù)組上進(jìn)行記錄和修改翔脱，更為節(jié)約內(nèi)存

• 做這樣的題目就像數(shù)學(xué)題一樣奴拦，先找到object之間的關(guān)系，再去推演自己想要的算法届吁。

• 位置示意圖

3.解決

class Solution:

    def maximalSquare(self, matrix):
        if not matrix or not matrix[0]:
            return 0
        m, n = len(matrix), len(matrix[0])
        dp = [[0] * n for _ in range(m)]
        ans = 0
        for i in range(m):
            for j in range(n):
                dp[i][j] = int(matrix[i][j])
                if i and j and dp[i][j]:
                    dp[i][j] = min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + 1
                ans = max(ans, dp[i][j])
        return ans * ans

• 直接在原數(shù)組上進(jìn)行修改粱坤，更為節(jié)約內(nèi)存

class Solution:

    def maximalSquare(self, matrix):
        if not matrix or not matrix[0]:
            return 0
        m, n = len(matrix), len(matrix[0])
        ans = 0
        for i in range(m):
            for j in range(n):
                matrix[i][j] = int(matrix[i][j])
                if i and j and matrix[i][j]:
                    matrix[i][j] = min(matrix[i - 1][j], matrix[i][j - 1], matrix[i - 1][j - 1]) + 1
                ans = max(ans, matrix[i][j])
        return ans * ans