Given a 2D binary matrix filled with 0’s and 1’s, find the largest square containing only 1’s and return its area.
Example:
Input: 1 0 1 0 0 1 0 1 1 1 1 1 1 1 1 1 0 0 1 0 Output: 4
给定一个0,1矩阵，问矩阵中最大的全是1的正方形的面积是多少。 使用DP求解，假设dp[i][j]表示以点(i,j)为右下角的正方形的最大边长，则有dp[i][j]=min(dp[i-1][j],dp[i][j-1],dp[i-1][j-1])+1。
对于点(i,j)，我们已经知道以该点的左边、上边和左上角的点为正方形右下角的点能得到的最大的正方形的边长。最好的情况是，如果这三个点能构成的最大正方形的边长相等，则加上点(i,j)之后，边长会扩大1。如下图红色的1，他的左边、上边和左上角的点为正方形右下角的点能得到的最大的正方形的边长都是2，所以加上该红色1之后，最大的边长变成了3。
0 0 0 0 0
0 1 1 1 0
0 1 1 1 0
0 1 1 1 0
0 0 0 0 0
再比如红色1的左边那个点的边长只有1，则红色1最多只能扩展成边长为1+1的正方形。所以这个递推公式是合理的：dp[i][j]=min(dp[i-1][j],dp[i][j-1],dp[i-1][j-1])+1。
0 0 0 0 0
0 1 1 1 0
0 1 1 1 0
0 0 1 1 0
0 0 0 0 0
有递推公式就好办了，直接O(n^2)DP，代码如下：
class Solution {
public:
int maximalSquare(vector<vector<char> >& matrix)
{
if (matrix.empty() || matrix[0].empty())
return 0;
int m = matrix.size(), n = matrix[0].size();
vector<vector<int> > dp(m, vector<int>(n, 0));
int maxLen = 0;
for (size_t i = 0; i < m; ++i) {
dp[i][0] = (matrix[i][0] == ‘1’ ? 1 : 0);
maxLen = max(maxLen, dp[i][0]);
}
for (size_t j = 0; j < n; ++j) {
dp[0][j] = (matrix[0][j] == ‘1’ ? 1 : 0);
maxLen = max(maxLen, dp[0][j]);
}
for (size_t i = 1; i < m; ++i) {
for (size_t j = 1; j < n; ++j) {
if (matrix[i][j] == ‘1’) {
dp[i][j] = min(min(dp[i][j – 1], dp[i – 1][j]), dp[i – 1][j – 1]) + 1;
maxLen = max(maxLen, dp[i][j]);
}
}
}
return maxLen * maxLen;
}
};本代码提交AC，用时6MS。
因为dp[i][j]实际上只和之前的三个值有关，所以可以节省空间。代码如下：
class Solution {
public:
int maximalSquare(vector<vector<char> >& matrix)
{
if (matrix.empty() || matrix[0].empty())
return 0;
int m = matrix.size(), n = matrix[0].size();
vector<int> dp(n + 1, 0);
int maxLen = 0, last_topleft = 0; // dp[i][j]的左上角那个值
for (size_t i = 1; i <= m; ++i) {
for (size_t j = 1; j <= n; ++j) {
int tmp = dp[j];
if (matrix[i – 1][j – 1] == ‘1’) {
dp[j] = min(min(dp[j], dp[j – 1]), last_topleft) + 1;
maxLen = max(maxLen, dp[j]);
}
else {
dp[j] = 0;
}
last_topleft = tmp;
}
}
return maxLen * maxLen;
}
};本代码提交AC，用时6MS。