@laigary.com~/interview/coding/221-maximal-square.md$
$ cat ./coding/221-maximal-square.md
[Coding]·2023-01-28·9 min read

221. Maximal Square

221. Maximal Square

在一個只有 '0' 和 '1' 的矩陣裡，找出全部由 '1' 組成的最大正方形，回傳它的面積。

思路

這個題目有動態規劃的最佳解，不過這個題目如果使用窮舉的話是不會超時的，所以我很建議可以就從窮舉來想，再看看能不能優化。

窮舉要枚舉什麼

題目給定的矩陣長寬是不定的，而假設今天如果題目的矩陣全部都是 1 ，那今天在這個矩陣長方形內，最大的正方形邊長一定是長或寬的短邊。

rows = len(matrix)
columns = len(matrix[0])
m = min(rows, columns)

這時候可以從兩個方向來寫

  1. 從最小的正方形邊長 1 開始檢查，一直檢查到最大的正方形邊長 m ，如果說一直到 m 都可以的話，那最大面積就會是 m2。
  2. 從最大的正方形邊長 m 開始檢查，一直檢查到最小的正方形邊長 1，如果存在一個正方形滿足題目條件，則馬上回傳面積。

我選擇的是第二條路，因為是窮舉法，又是要找最大，我當然是趕快找到最大的正方形就好。

從窮舉變成 DP

如果從左上往右下開始找尋最大的正方形，一定是首先自己的位置要是 1 ，接著，去看可以來到這個位置的三個方向：上、左、左上去看看是不是都是 1 ，但是這樣我們還要繼續往回找，看看是不是都是 1 ，因此最好的方法應該是在找尋的時候，就順便記錄起來。

至於紀錄的方式，就是我們看左上、上、左，可以形成的最大正方形中，哪一個最小，動態轉移方程式就是：

dp[row][col] = min(dp[row-1][col], dp[row][col-1], dp[row-1][col-1]) + 1

取 min 是這題的全部。 dp[row][col] 的定義是「以這一格為右下角的最大正方形邊長」，而要讓邊長變成 k，上、左、左上三個方向都必須撐得住 k - 1 —— 只要有一個撐不住，整個正方形就缺一角。所以是三者取最小再加一，不是取最大。

解題方向

窮舉法

class Solution:
    def maximalSquare(self, matrix: List[List[str]]) -> int:
        rows = len(matrix)
        columns = len(matrix[0])
        L = min(rows, columns) # Shorter Side

        def is_square(row, col, length):
            i = row
            while i < (row + length):
                j = col
                while j < (col + length):
                    if matrix[i][j] == '0':
                        return False
                    j += 1
                i += 1
            return True

        while L > 0: 
            i = 0
            while i < rows - L + 1:
                j = 0
                while j < columns - L + 1:
                    if is_square(i, j, L):
                        return L ** 2
                    j += 1
                i += 1
            L -= 1
        return 0

動態規劃

class Solution:
    def maximalSquare(self, matrix: List[List[str]]) -> int:
        rows = len(matrix)
        columns = len(matrix[0])
        dp = [[0] * (columns + 1) for _ in range(rows + 1)]
        m = 0
        for row in range(1, rows + 1):
            for col in range(1, columns + 1):
                if matrix[row-1][col-1] == '1':
                    dp[row][col] = min(dp[row-1][col], dp[row][col-1], dp[row-1][col-1]) + 1
                    m = max(dp[row][col], m)

        return m ** 2

dp 開成 (rows + 1) x (columns + 1)，多出來的第 0 列和第 0 行是邊界哨兵 —— 它們永遠是 0，這樣第一列和第一行在讀 dp[row-1]、dp[col-1] 時就不必特判越界。代價是索引錯開一格，所以矩陣要寫成 matrix[row-1][col-1]。

補充

窮舉法的成本非常吃測資

return L ** 2 那個提早回傳，讓這一版的表現在不同矩陣上差很多：

  • 全部都是 1 —— 第一次檢查（最大的邊長、左上角）就中，幾乎不用跑
  • 全部都是 0 —— 每次 is_square 在第一格就失敗，所以每次檢查是 O(1)，只有位置數的成本
  • 最慢的是「到處都是差一點點的正方形」 —— 這時候 is_square 每次都要掃過大半個正方形才發現有一格是 0，而且掃完還找不到答案，只能繼續往下一個邊長試

也就是說「窮舉不會超時」這件事是靠測資的形狀，不是靠演算法。面試時值得主動講這一點，然後再接到 DP。

複雜度

設 R、C 是矩陣的長寬，K=min⁡(R,C) 是可能的最大邊長。

窮舉法

  • 時間 最壞 O(R×C×K3) — 邊長有 K 種，每種要試 O(R×C) 個位置，每次檢查最多 K2 格
  • 空間 O(1) — 只用了幾個索引

動態規劃

  • 時間 O(R×C) — 每一格算一次，每次都是 O(1)
  • 空間 O(R×C) — dp 表的大小；因為只依賴上一列，滾動成一維可以降到 O(C)

窮舉那個上界實務上碰不到（提早失敗和提早回傳都會砍掉大量工作），但它說明了為什麼這題最後還是要走 DP：DP 把「每個正方形都重新驗一次」變成「每一格只算一次」。

--tags#Dynamic Programming
← cd ../codingcd ~