---
title: "221. Maximal Square"
url: "https://laigary.com/interview/coding/221-maximal-square"
type: "note"
section: "coding"
date: "2023-01-28"
updated: "2026-08-03"
tags: ["Dynamic Programming"]
---

# 221. Maximal Square

[221\. Maximal Square](https://leetcode.com/problems/maximal-square/)

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

## 思路

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

### 窮舉要枚舉什麼

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

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

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

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

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

### 從窮舉變成 DP

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

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

```python
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` —— 只要有一個撐不住，整個正方形就缺一角。所以是三者取最小再加一，不是取最大。

## 解題方向

### 窮舉法

```python
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
```

### 動態規劃

```python
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 \times C \times K^3)$ — 邊長有 $K$ 種，每種要試 $O(R \times C)$ 個位置，每次檢查最多 $K^2$ 格
- 空間 $O(1)$ — 只用了幾個索引

**動態規劃**
- 時間 $O(R \times C)$ — 每一格算一次，每次都是 $O(1)$
- 空間 $O(R \times C)$ — `dp` 表的大小；因為只依賴上一列，滾動成一維可以降到 $O(C)$

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