221. Maximal Square

Medium
Description

給定一個由 '0' 和 '1' 組成的二維矩陣，找出只包含 '1' 的最大正方形，回傳其面積。

Example:

Input: matrix = [[“1”,“0”,“1”,“0”,“0”],[“1”,“0”,“1”,“1”,“1”],[“1”,“1”,“1”,“1”,“1”],[“1”,“0”,“0”,“1”,“0”]] Output: 4

Intuition#

  • 若 matrix[i][j] == '1'，則 dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1
  • 直覺：正方形受限於三個方向中最弱的一邊
  • 追蹤全域最大邊長，最後回傳面積

Approaches#

1: 2D DP#

  • 概念: 建立 dp 表格，每個 '1' 格子的值由左、上、左上的最小值決定。
  • 時間複雜度: O(m * n)
  • 空間複雜度: O(m * n)
class Solution {
    fun maximalSquare(matrix: Array<CharArray>): Int {
        val m = matrix.size
        val n = matrix[0].size
        val dp = Array(m + 1) { IntArray(n + 1) }
        var maxSide = 0

        for (i in 1..m) {
            for (j in 1..n) {
                if (matrix[i - 1][j - 1] == '1') {
                    dp[i][j] = minOf(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + 1
                    maxSide = maxOf(maxSide, dp[i][j])
                }
            }
        }
        return maxSide * maxSide
    }
}

⭐2: 1D DP（空間優化）#

  • 概念: 只用一維陣列加一個變數記錄左上角的值。
  • 時間複雜度: O(m * n)
  • 空間複雜度: O(n)
class Solution {
    fun maximalSquare(matrix: Array<CharArray>): Int {
        val m = matrix.size
        val n = matrix[0].size
        val dp = IntArray(n + 1)
        var maxSide = 0
        var prev = 0

        for (i in 1..m) {
            for (j in 1..n) {
                val temp = dp[j]
                if (matrix[i - 1][j - 1] == '1') {
                    dp[j] = minOf(dp[j], dp[j - 1], prev) + 1
                    maxSide = maxOf(maxSide, dp[j])
                } else {
                    dp[j] = 0
                }
                prev = temp
            }
            prev = 0
        }
        return maxSide * maxSide
    }
}

🔑 Takeaways#

  • Pattern: 矩陣型 DP — 以每格為右下角計算最大正方形
  • 關鍵技巧: 「木桶效應」— 正方形邊長受三個方向最小值限制；注意用 (m+1) x (n+1) 大小避免邊界判斷