題目來(lái)源
Given a 2D binary matrix filled with 0's and 1's, find the largest square containing only 1's and return its area.
For example, given the following matrix:
1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0
Return 4.
尋找最大矩形知市。想到應(yīng)該用DP派昧，但是還沒(méi)想到應(yīng)該怎么用。
突然想到之前做過(guò)找最大長(zhǎng)方形的，也可以用類似的方法湾盒。想想不行埋哟。
然后想想利用dp[i][j]和dp[i-1][j-1]的關(guān)系也是可行的。
class Solution {
public:
int maximalSquare(vector<vector<char>>& matrix) {
int m = matrix.size();
if (m == 0)
return 0;
int n = matrix[0].size();
vector<vector<int>> dp(m+1, vector<int>(n+1, 0));
for (int i=1; i<=m; i++)
for (int j=1; j<=n; j++) {
if (matrix[i-1][j-1] == '0')
dp[i][j] = 0;
else {
dp[i][j]++;
for (int k=1; k<=dp[i-1][j-1]; k++) {
if (matrix[i-k-1][j-1] != '1' || matrix[i-1][j-k-1] != '1')
break;
dp[i][j]++;
}
}
}
int res = 0;
for (int i=1; i<=m; i++)
for (int j=1; j<=n; j++)
res = max(res, dp[i][j] * dp[i][j]);
return res;
}
};
看了看討論區(qū)坐梯，發(fā)現(xiàn)可以改進(jìn)，直接如下：
class Solution {
public:
int maximalSquare(vector<vector<char>>& matrix) {
int m = matrix.size();
if (m == 0)
return 0;
int n = matrix[0].size();
int res = 0;
vector<vector<int>> dp(m+1, vector<int>(n+1, 0));
for (int i=1; i<=m; i++)
for (int j=1; j<=n; j++) {
if (matrix[i-1][j-1] == '0')
dp[i][j] = 0;
else {
dp[i][j] = min(dp[i-1][j-1] + 1, min(dp[i-1][j], dp[i][j-1]) + 1);
res = max(res, dp[i][j] * dp[i][j]);
}
}
return res;
}
};
