Maximal Square
Given a 2D binary matrix filled with 0's and 1's, find the largest square containing all 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 0Return 4.
Credits:
Special thanks to @Freezen for adding this problem and creating all test cases.
Hide Tags
Dynamic Programming
Hide Similar Problems
(H) Maximal Rectangle
先借用 085题 Maximal Rectangle 的思路，转成直方图，取小边计算正方形面积，
确实可以通过，不过性能不咋地（28 ms）。
看标签是DP，那就重新DP吧。
一开始总想着经典的 DP，每一个格子保存最大可能的结果，不断滚动到最后一个格子就得到了结果。
但一旦把最大可能继承下来，后续就可能出现无法判断是不是成了正方形的情况，例如 110, 111, 011。
比划了好一阵子，按照自己为 0/1 ，以及左边，上面，左上分别为 0/1 的情况来组合的话，还挺复杂的。
看来这样是行不通，首先必须保证如果自己是 0，填入的数字能清楚地标识累积的中断，最好的方式就是把自己直接置 0。
但自己为 1 的情况，并不是所有的情况都能够直接累加 1 的，搞得还有点绕：
必须左边，上面，左上必须同时不为 0（自己也为 1），才意味着正方形边长递增 1。
但是并不是所有的时候，这三个里存储的数值都一样，有时候会有些不同。
画实际的例子分析的结果是，先看左边和上边是不是相等，如果相等，看起来应该是继承它们和左上之间较小的数字再加一。
如果不相等，看起来是继承这两者之间较小的数字再加一。
考虑完三个全为 1 的情况，还要考虑如果有一个或者几个为 0，就不能递增了。那是该继承呢，还是？
一开始不大确定，直到搞了个坐标继承的思路，分别从左/上继承 y, x 坐标，才意识到一个 0 会直接祸害右/下/右下的 1，
也就是说，一个 0 的存在，它的右/下/右下都应该直接置为 1。
或者，反过来说，一个元素如果为 1，但其左/上/左上不全为 1 的话，它就得置为 1 了（不像传统 DP 里滚动保存最大的可能）。
然后按照这样的规则，得到了最终应该填入格子的值（也就是正方形的边长）的时候，
就可以比较一下，是不是这个值的平方更大？是的话就更新结果。
全部处理完所有的格子，也就知道了最大的可能结果。
但不同于传统的DP，它不是出现在最后一个格子，而是在中间的某个地方。
按照这个思路写完代码提交，accepted，12 ms，果然是这么个道道！
跟着就是简化代码了，首先是合并各种情况：
既然全为一的时候是取最小值，那两种情况的最小值是不是都是三者中最小的呢？从实际画图分析，是的！
所以，将其合并为直接求三者的最小值再加一，得到了第二版的代码。
再看，最小值的前面的条件(fa&&fb&&fc)似乎不是很必要，如果三者中有个 0，最小值也自然是 0 了，不必多一个保护。
所以去掉它，得到第三版的代码。
最后，还可以写得在简略一点，去掉判断 sz zz 是否大于零的条件，因为如果他们为 0，for 循环也就自然不走了。
这样得到最后的版本。
实际上还可以简化一步：更新 rst 的时候，只需要更新边长，最后 return 的时候，返回 rst*rst 计算一次面积就好了。
class Solution {
public:
//------------------------------ 第一版 ------------------------------
int maximalSquare(vector<vector<char>>& matrix) {
int rst = 0;
int sz = matrix.size();
if(sz)
{
int zz=matrix[0].size();
if(zz)
{
vector<vector<int>> flags(sz, vector<int>(zz));
for(int ii=0; ii<sz; ++ii)
{
for(int jj=0; jj<zz; ++jj)
{
int d = matrix[ii][jj] - '0';
int fa = (ii&&jj) ? flags[ii-1][jj-1] : 0;
int fb = (ii) ? flags[ii-1][jj] : 0;
int fc = (jj) ? flags[ii][jj-1] : 0;
int ff = fa&&fb&&fc;
int tmp=0;
if(d)
{
if(ff)
{
if(fb==fc)
tmp=min(fa, fb)+1;
else
tmp=min(fb, fc)+1;
}
else
tmp = 1;
}
flags[ii][jj] = tmp;
rst = max(rst, tmp*tmp);
}
}
}
}
return rst;
}
//------------------------------ 第二版 ------------------------------
int maximalSquare(vector<vector<char>>& matrix) {
int rst = 0;
int sz = matrix.size();
if(sz)
{
int zz=matrix[0].size();
if(zz)
{
vector<vector<int>> flags(sz, vector<int>(zz));
for(int ii=0; ii<sz; ++ii)
{
for(int jj=0; jj<zz; ++jj)
{
int fa = (ii&&jj) ? flags[ii-1][jj-1] : 0;
int fb = (ii) ? flags[ii-1][jj] : 0;
int fc = (jj) ? flags[ii][jj-1] : 0;
flags[ii][jj] = (matrix[ii][jj]>'0') ? (1+(fa&&fb&&fc)*min(fa, min(fb, fc))) : 0;
rst = max(rst, flags[ii][jj]*flags[ii][jj]);
}
}
}
}
return rst;
}
//------------------------------ 第三版 ------------------------------
int maximalSquare(vector<vector<char>>& matrix) {
int rst = 0;
int sz = matrix.size();
if(sz)
{
int zz=matrix[0].size();
if(zz)
{
vector<vector<int>> flags(sz, vector<int>(zz));
for(int ii=0; ii<sz; ++ii)
{
for(int jj=0; jj<zz; ++jj)
{
int fa = (ii&&jj) ? flags[ii-1][jj-1] : 0;
int fb = (ii) ? flags[ii-1][jj] : 0;
int fc = (jj) ? flags[ii][jj-1] : 0;
flags[ii][jj] = (matrix[ii][jj] > '0') ? (min(fa, min(fb, fc))+1) : 0;
rst = max(rst, flags[ii][jj]*flags[ii][jj]);
}
}
}
}
return rst;
}
//------------------------------ 第四版 ------------------------------
int maximalSquare(vector<vector<char>>& matrix) {
int rst = 0;
for(int ii=0; ii<matrix.size(); ++ii)
{
for(int jj=0; jj<matrix[0].size(); ++jj)
{
int fa = (ii&&jj) ? matrix[ii-1][jj-1] : 0;
int fb = (ii) ? matrix[ii-1][jj] : 0;
int fc = (jj) ? matrix[ii][jj-1] : 0;
matrix[ii][jj] = (matrix[ii][jj]>'0') ? (min(fa, min(fb, fc))+1) : 0;
rst = max(rst, matrix[ii][jj]*matrix[ii][jj]); //实际上不用算面积，更新边长就可以了。
}
}
return rst; //如果更新边长，这里就返回 rst*rst。
}
};
12 ms
No comments:
Post a Comment