題目描述:給定僅含 '0' 和 '1' 的二維矩陣,找出只包含 '1' 的最大正方形面積。
解題思路:DP:dp[i][j] = 以 (i,j) 為右下角、只含 '1' 的最大正方形邊長。轉移公式:若 matrix[i][j] == '1',則 dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1。直觀理解:三個方向的最小值決定了可擴展的邊長。答案為所有 dp 值的最大值的平方。
時間複雜度:O(m × n) — 遍歷整個矩陣一次。
空間複雜度:O(m × n) — DP 表,可優化為 O(n) 滾動陣列(只需前一行)。
1. Initialize dp[m+1][n+1] = 0, maxSide = 0
2. For i from 1 to m:
For j from 1 to n:
If matrix[i-1][j-1] == '1':
dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1
maxSide = max(maxSide, dp[i][j])
3. Return maxSide * maxSide暴力枚舉 O(m × n × min(m,n)):對每個格子試所有可能邊長,驗證是否全為 '1' — 正確但過慢。
柱狀圖 + 單調棧 O(m × n):對每行建立高度柱狀圖,找最大全 '1' 正方形(類似 LC 85 矩形問題但限定為正方形)— 等效但實作更複雜。
滾動陣列 O(n) 空間優化:只保留前一行的 dp 值,額外用一個 prev 變數暫存 dp[i-1][j-1]。