給定一個由
'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
TIP
dp[i][j] 表示以 (i,j) 為右下角的最大正方形邊長，取決於左、上、左上三個鄰居的最小值加一。
- 若
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 — O(m * n) / O(m * n)
- Idea: 建立
dp表格，每個'1'格子的值由左、上、左上的最小值決定。 - Time:
O(m * n) - Space:
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 (Space Optimized) — O(m * n) / O(n)
- Idea: 只用一維陣列加一個變數記錄左上角的值。
- Time:
O(m * n) - Space:
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 — 以每格為右下角計算最大正方形
- Key trick: 「木桶效應」— 正方形邊長受三個方向最小值限制；注意用
(m+1) x (n+1)大小避免邊界判斷