题目说明
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.
题目分析
我采用的方法比较笨拙，就是对于矩阵中的每一个元素，以反“L”型不断向右下扩增，以确定最大正方形的面积。
以下为个人实现（C++，25ms）：
class Solution {
public:
int maximalSquare(vector<vector<char>>& matrix) {
int row = matrix.size();
int max_a = 0;
for (int i = 0; i < row; i++) {
int col = matrix[i].size();
for (int j = 0; j < col; j++) {
if (matrix[i][j] - '0') {
int a;
for (a = 1; i + a < row && j + a < col; a++) { // overflow judge
int off_x, off_y;
// go through in 'L' shape
for (off_x = 0; off_x < a + 1 && matrix[i + a][j + off_x] - '0'; off_x++);
if (off_x < a + 1) {
break;
}
for (off_y = 0; off_y < a + 1 && matrix[i + off_y][j + a] - '0'; off_y++);
if (off_y < a + 1) {
break;
}
}
if (a > max_a) {
max_a = a;
}
}
}
}
return max_a * max_a;
}
};
毫无疑问这种解决方式太慢了。实际上我对很多点进行了重复判断，比如一个大正方形内部包含的若干小真方形，我都用“L”扩增的方式进行了判断，这种情况应该使用DP解决。
DP实现代码（C++，原贴）：
int maximalSquare(vector<vector<char>>& matrix) {
if (matrix.empty()) return 0;
int m = matrix.size(), n = matrix[0].size();
vector<int> dp(m + 1, 0);
int maxsize = 0, pre = 0;
for (int j = 0; j < n; j++) {
for (int i = 1; i <= m; i++) {
int temp = dp[i];
if (matrix[i - 1][j] == '1') {
dp[i] = min(dp[i], min(dp[i - 1], pre)) + 1;
maxsize = max(maxsize, dp[i]);
}
else dp[i] = 0;
pre = temp;
}
}
return maxsize * maxsize;
}
如果有一个边长为n（n>=2）的正方形，那么它的内部一定存在4个边长为n-1的正方形。于是代码实现的思路是如果某元素值为1，那么取其左元素、上元素和左上元素中的边长最小值+1，得到的结果就可以作为该元素的边长，否则该元素边长为0。