在一個(gè)由 0 和 1 組成的二維矩陣內(nèi)逸绎，找到只包含 1 的最大正方形筋粗，并返回其面積。
輸入:
1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0
輸出: 4
方法二：動態(tài)規(guī)劃
方法一雖然直觀攀甚，但是時(shí)間復(fù)雜度太高吞瞪，有沒有辦法降低時(shí)間復(fù)雜度呢馁启？
可以使用動態(tài)規(guī)劃降低時(shí)間復(fù)雜度。我們用 dp(i, j)dp(i,j) 表示以 (i, j)(i,j) 為右下角芍秆，且只包含 11 的正方形的邊長最大值惯疙。如果我們能計(jì)算出所有 dp(i, j)dp(i,j) 的值，那么其中的最大值即為矩陣中只包含 11 的正方形的邊長最大值妖啥，其平方即為最大正方形的面積霉颠。
那么如何計(jì)算 dpdp 中的每個(gè)元素值呢？對于每個(gè)位置 (i, j)(i,j)荆虱，檢查在矩陣中該位置的值：
如果該位置的值是 00蒿偎，則 dp(i, j) = 0dp(i,j)=0，因?yàn)楫?dāng)前位置不可能在由 11 組成的正方形中怀读；
如果該位置的值是 11诉位，則 dp(i, j)dp(i,j) 的值由其上方、左方和左上方的三個(gè)相鄰位置的 dpdp 值決定菜枷。具體而言不从，當(dāng)前位置的元素值等于三個(gè)相鄰位置的元素中的最小值加 11，狀態(tài)轉(zhuǎn)移方程如下：
dp(i, j)=min(dp(i?1, j), dp(i?1, j?1), dp(i, j?1))+1
dp(i,j)=min(dp(i?1,j),dp(i?1,j?1),dp(i,j?1))+1
如果讀者對這個(gè)狀態(tài)轉(zhuǎn)移方程感到不解犁跪，可以參考 1277. 統(tǒng)計(jì)全為 1 的正方形子矩陣的官方題解，其中給出了詳細(xì)的證明歹袁。
此外坷衍，還需要考慮邊界條件。如果 ii 和 jj 中至少有一個(gè)為 00条舔，則以位置 (i, j)(i,j) 為右下角的最大正方形的邊長只能是 11枫耳，因此 dp(i, j) = 1dp(i,j)=1。
以下用一個(gè)例子具體說明孟抗。原始矩陣如下迁杨。
0 1 1 1 0
1 1 1 1 0
0 1 1 1 1
0 1 1 1 1
0 0 1 1 1
對應(yīng)的 dpdp 值如下。
0 1 1 1 0
1 1 2 2 0
0 1 2 3 1
0 1 2 3 2
0 0 1 2 3
下圖也給出了計(jì)算 dpdp 值的過程凄硼。
class Solution {
public:
int maximalSquare(vector<vector<char>>& matrix) {
if (matrix.size() == 0 || matrix[0].size() == 0) {
return 0;
}
int maxSide = 0;
int rows = matrix.size(), columns = matrix[0].size();
vector<vector<int>> dp(rows, vector<int>(columns));
for (int i = 0; i < rows; i++) {
for (int j = 0; j < columns; j++) {
if (matrix[i][j] == '1') {
if (i == 0 || j == 0) {
dp[i][j] = 1;
} else {
dp[i][j] = min(min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1;
}
maxSide = max(maxSide, dp[i][j]);
}
}
}
int maxSquare = maxSide * maxSide;
return maxSquare;
}
};
復(fù)雜度分析
時(shí)間復(fù)雜度：O(mn)O(mn)铅协，其中 mm 和 nn 是矩陣的行數(shù)和列數(shù)。需要遍歷原始矩陣中的每個(gè)元素計(jì)算 dp 的值摊沉。
空間復(fù)雜度：O(mn)O(mn)狐史，其中 mm 和 nn 是矩陣的行數(shù)和列數(shù)。創(chuàng)建了一個(gè)和原始矩陣大小相同的矩陣 dp。由于狀態(tài)轉(zhuǎn)移方程中的 dp(i, j)dp(i,j) 由其上方骏全、左方和左上方的三個(gè)相鄰位置的 dpdp 值決定苍柏，因此可以使用兩個(gè)一維數(shù)組進(jìn)行狀態(tài)轉(zhuǎn)移，空間復(fù)雜度優(yōu)化至 O(n)O(n)姜贡。
