LeetCode 221：最大正方形——動態規劃求全 1 正方形最大面積

題目描述

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

DP 狀態定義

dp[i][j] 表示以 (i-1, j-1) 為右下角的全 1 正方形的邊長。（矩陣下標從 1 起便於邊界處理）

狀態轉移

• 若 matrix[i-1][j-1] == '0'，dp[i][j] = 0。
• 若為 '1'，正方形可由左、上、左上三個鄰居擴展而來：
  dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1。

C++ 實現（空間優化至 O(n)）

class Solution {
public:
    int maximalSquare(vector<vector<char>>& matrix) {
        if (matrix.empty()) return 0;
        int m = matrix.size(), n = matrix[0].size();
        vector<int> dp(n+1, 0);
        int maxSide = 0, prev = 0;
        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                int temp = dp[j];
                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;
            }
        }
        return maxSide * maxSide;
    }
};

關鍵點

• prev 保存左上角值（上一輪的 dp[j-1]）。
• 滾動陣列將空間從 O(mn) 降至 O(n)。
• 最終面積為 maxSide²。

複雜度

• 時間：O(mn)。
• 空間：O(n)。