🟨最大正方形

本題取自 Leetcode 221. Maximal Square

題目

Given an m x n binary matrix filled with 0's and 1's, find the largest square containing only 1's and return its area.

Example 1:

Input: matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
Output: 4

Example 2:

Input: matrix = [["0","1"],["1","0"]]
Output: 1

Example 3:

Input: matrix = [["0"]]
Output: 0
 

Constraints:

m == matrix.length
n == matrix[i].length
1 <= m, n <= 300
matrix[i][j] is '0' or '1'.

分析

題目要找出矩陣中，內部只包含'1'的最大的正方形面積。

分治法

考慮矩陣的第(i.j)格。以這格為右下角的最大正方形，其邊長為多少？

例如下圖綠底這格，其答案為2

遍歷整個矩陣，並求每一格答案之最大值，即可得最大的正方形面積。

設計狀態、找出轉移式與最小問題

狀態：定義 maxSq(i,j)：

以矩陣的第(i.j)格為最右下角的最大正方形，其邊長。

轉移式

若matrix[i][j]=='0'，則這格不在任何正方形內， maxSq(i,j) = 0

若matrix[i][j]=='1'，則要進一步分析：

假設有一個邊長為k的正方形。若我們切掉右下角一格，則剩下的圖形能夠切出多大的正方形呢？

很顯然是k-1：

如果某格的答案為k(代表至少有一邊長為k的正方形)，則這格左上角、上方、左方一格的答案都應該至少為k-1

反過來想，若我們知道某一格左上角、上方、左方一格的答案，則右下角這一格的答案應該要怎麼求出來呢？

例如，考慮這個局部，數字是已求出的子問題答案(maxSq)：

根據我們對子問題的定義，可以知道周圍的圖形應該長這個樣子：

那麼問號這格的答案，很顯然應該是3

觀察之後，可以發現這個答案受限於上面這格的2，也就是說，子問題的答案受到左上角、上方、左方一格的答案之中的最小值的限制

某格的答案應為：左上角、上方、左方一格的答案之中的最小值 + 1

分析至此，我們終於可以得到完整的轉移式：

if matrix[i][j]=='0':
    maxSq(i,j) = 0
else: # (matrix[i][j]==1)
    maxSq(i,j) = 1 + min(
        maxSq(i-1, j-1) , maxSq(i-1, j) , maxSq(i, j-1)
    )

邊界條件：

當計算最上一列或者最左一行的子問題答案時(i==0 or j==0)，最大只會有邊長為1的正方形，因此maxSq(i,j) = matrix[i][j]

題目所求(母問題答案)：

題目所求為所有maxSq(i,j)中答案最大值的平方(求面積)

實作

Top-Down DP

class Solution:
    def maximalSquare(self, matrix: List[List[str]]) -> int:
        @cache
        def maxSq(i,j): # 以(i,j)為右下角的最大正方形邊長
            #  無正方形
            if matrix[i][j]=='0': return 0
            #  有正方形 (matrix[i][j]=='1')
            ## 最上一列 or 最左一行
            if i==0 or j==0: return 1
            ## 一般式
            return 1 + min(maxSq(i-1,j-1), maxSq(i-1,j), maxSq(i,j-1))
        # 回答：所有子問題之中答案最大者的平方
        return max(maxSq(i,j) for i in range(len(matrix)) for j in range(len(matrix[0]))) ** 2

Bottom-Up DP

class Solution:
    def maximalSquare(self, matrix: List[List[str]]) -> int:
        m,n = len(matrix), len(matrix[0])
        # 記錄子問題答案用的矩陣
        dp = [[0 for j in range(n)] for i in range(m)]
        maxAns = 0
        # 由上到下、由左到右計算每一格的子問題答案maxSq(i,j)並記錄於dp[i][j]
        for i in range(m):
            for j in range(n):
                #  無正方形
                if matrix[i][j]=='0': continue
                #  有正方形
                ## 最上一列or最左一行 
                if i==0 or j==0: 
                    dp[i][j] = 1
                ## 一般轉移式
                else:
                    dp[i][j] = 1 + min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1])
                # 更新答案的最大值
                if dp[i][j]>maxAns:
                    maxAns = dp[i][j]
        # 回答：所有子問題之中答案最大者的平方
        return maxAns **2

因為狀態轉移只跟前一行、前一列的答案有關，本題也可以使用Rolling Bottom-Up DP

class Solution:
    def maximalSquare(self, matrix: List[List[str]]) -> int:
        m,n = len(matrix), len(matrix[0])
        # 記錄子問題答案用的矩陣
        dp = [0]*n
        maxAns = 0
        # 由上到下、由左到右計算每一格的子問題答案maxSq(i,j)並記錄於dp2[j]
        for i in range(m):
            dp2=[]
            for j in range(n):
                #  無正方形
                if matrix[i][j]=='0': 
                    ans = 0
                #  有正方形
                ## 最上一列or最左一行 
                elif i==0 or j==0: 
                    ans = 1
                ## 一般轉移式
                else:
                    ans = 1 + min(dp[j-1], dp[j], dp2[j-1])
                # 更新答案的最大值
                if ans > maxAns:
                    maxAns = ans
                dp2.append(ans)
            # Rolling
            dp = dp2
        # 回答：所有子問題之中答案最大者的平方
        return maxAns **2

複雜度分析

時間複雜度

時間複雜度 = 狀態轉移數 x 計算複雜度

本題的狀態數 = O(n^2)，計算複雜度 = O(1)

因此時間複雜度 = O(n^2)

空間複雜度

因為需要記住每題子問題的答案，空間複雜度 = 狀態數 = O(n^2)

如果使用Rolling的bottom-up，則空間複雜度 = O(n)

結語

和前兩天的矩陣問題不同，並非路徑相關的問題，而是和圖形判斷有關。

在這三天實作的過程我們可發現，矩陣題型有一些相似處：

• 狀態轉移和左方一格、上方一格有關(今天的題目還多了左上一格)
• 處理邊界條件時，需要考慮index超出邊界的情況
• Bottom-Up迭代的順序可以照著原矩陣的順序(例如筆者的範例解答，均從上到下並從左到右迭代)
• 可使用Rolling的技巧來幫Bottom-Up降低一個維度的空間複雜度

日後我們開始解Hard題時就會發現，許多進階的DP題都是結合基本題型和其他的演算法或者資料型態。

若能熟悉基本題型的共同點，並且掌握實作時需要注意的地方，在解進階題時會非常有幫助。

以上為Day08的內容！感謝你的閱讀，如果有不同的想法或心得，歡迎留言一同討論！

本文也同步登載在我的個人部落格，記錄我的學習筆記與生活點滴，歡迎來逛逛。

明天會開始看字串類型的問題。