目錄

🟨最大正方形

本題取自 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

alt text

Example 2:

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

alt text

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

alt text

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

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

狀態:定義 maxSq(i,j)

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

轉移式

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

matrix[i][j]=='1',則要進一步分析:

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

很顯然是k-1

alt text

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

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

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

alt text

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

alt text

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

alt text

觀察之後,可以發現這個答案受限於上面這格的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)

如果使用Rollingbottom-up則空間複雜度 = O(n)

結語

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

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

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

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

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


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

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

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