LeetCode Maximal Square：動態規劃求全 1 最大正方形

問題描述

給定二維二值矩陣（'0'/'1'），找出只包含 '1' 的最大正方形，返回其面積。

示例：

1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0
輸出: 4 (2×2 正方形)

動態規劃狀態定義

dp[i][j] = 以 (i,j) 為右下角的全 1 正方形的最大邊長。
答案 = max(dp[i][j])²。

狀態轉移方程

• 若 matrix[i][j] == '0'：dp[i][j] = 0
• 若 matrix[i][j] == '1'：

  dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1
  

直觀理解

要在 (i,j) 形成邊長 k 的正方形，其上、左、左上三個鄰居必須至少能形成邊長 k-1 的正方形。取最小值 +1 保證新擴展的行和列全為 1。

邊界初始化

• 第一行 dp[0][j] = matrix[0][j] - '0'
• 第一列 dp[i][0] = matrix[i][0] - '0'

代碼實現（空間優化至 O(n)）

class Solution {
public:
    int maximalSquare(vector>& matrix) {
        if (matrix.empty() || matrix[0].empty()) return 0;
        int m = matrix.size(), n = matrix[0].size();
        vector dp(n + 1, 0); // 多一個哨兵簡化邊界
        int maxSide = 0, prev = 0; // prev 存儲 dp[i-1][j-1] (左上)
        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                int temp = dp[j]; // 暫存舊 dp[j] (即 dp[i-1][j]，下一輪的 prev)
                if (matrix[i-1][j-1] == '1') {
                    dp[j] = min({dp[j-1], dp[j], prev}) + 1; // 左、上、左上
                    maxSide = max(maxSide, dp[j]);
                } else {
                    dp[j] = 0;
                }
                prev = temp; // 更新 prev 為當前行的左上
            }
        }
        return maxSide * maxSide;
    }
};

空間優化關鍵：一維 DP + prev 變量

二維 dp[i][j] 只依賴 dp[i-1][j]（上）、dp[i][j-1]（左）、dp[i-1][j-1]（左上）。
一維數組 dp[j] 滾動存儲「上」的值，dp[j-1] 是「左」，prev 保存「左上」。

複雜度

• 時間：O(mn)
• 空間：O(n)（優化前 O(mn)）

與 Maximal Rectangle 的關係

• Maximal Square：正方形，DP 狀態簡單，O(mn) 時間。
• Maximal Rectangle：矩形，需單調棧，O(mn) 時間但邏輯更複雜。
• 本質上：正方形是矩形的特例，但算法思路不同（DP vs 直方圖）。

總結

Maximal Square 是二維 DP 經典入門題。關鍵在於狀態定義為「以 (i,j) 為右下角的最大正方形邊長」，轉移方程 min(上,左,左上)+1 精妙地捕捉了正方形擴展的幾何約束。一維空間優化是面試加分項。