221. Maximal Square --M !!!

Given an m x n binary matrix filled with 0's and 1's, find the largest square containing only 1's and return its area.

 

Example 1:

Input: matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
Output: 4

Example 2:

Input: matrix = [["0","1"],["1","0"]]
Output: 1

Example 3:

Input: matrix = [["0"]]
Output: 0

 

Constraints:

• m == matrix.length
• n == matrix[i].length
• 1 <= m, n <= 300
• matrix[i][j] is '0' or '1'.

A: 

首先的思考就是2D， 计算到该点的所有的1 的个数。 。然后对比现有边长更长一步的， 计算面积差。 如果满足R * R, 边长就可以增加了。

class Solution {

public:

int maximalSquare(vector<vector<char>>& matrix) {

int m = matrix.size(), n = matrix[0].size();

vector<vector<int>> M(m, vector<int>(n, 0)); // record the tota area

int maxR = 0; // maximum radium of the square

for (int i = 0; i < m; i++) {

for (int j = 0; j < n; j++) {

int up = i > 0 ? M[i - 1][j] : 0;

int left = j > 0 ? M[i][j - 1] : 0;

int diagonal = (i > 0 && j > 0) ? M[i - 1][j - 1] : 0;

M[i][j] = (matrix[i][j] == '0' ? 0 : 1) + up + left - diagonal;

// every time, we need at most increase R by one

int R = maxR + 1; // next possible increase of square edge

up = i - R >= 0 ? M[i - R][j] : 0;

left = j - R >= 0 ? M[i][j - R] : 0;

int d = (i - R >= 0 && j - R >= 0) ? M[i - R][j - R] : 0;

if (M[i][j] - (up + left - d) == R * R) {

maxR++;

}

}

}

return maxR * maxR;

}

};

-------------------------------------第二遍---------------------------------------------

思路参考 maximal rectangle。  仍然搞了个 height 的一位数组。  复杂的O(n*m)

class Solution {
public:
    int maximalSquare(vector<vector<char>>& matrix) {
        int m = matrix.size();
        if(m==0)
            return 0;
        int n = matrix[0].size();
        int maxEdge = 0; // the edge length of the result square
        vector<int> height(n,0);
        for(int i =0;i<m;++i)
        {
            for(int j =0;j<n;++j)
                height[j]  = matrix[i][j] =='0'? 0:++height[j];
            // calculate square at current height
            int left = 0, right =0;
            for(int right = 0; right < n;++right)
            {
                if(height[right]<=maxEdge)
                {
                    left = right+1; // cannot be this one, check from next position
                }else{
                    if(maxEdge < right - left +1)
                    {
                        maxEdge++;//break since for each row, maxEdge increase by at most 1
                        break; 
                    }
                }
            }
            
        }
        return maxEdge*maxEdge;
    }
};

Mistakes:
1:   因为每次maxLen会更改。因此，下一次比较的时候，maxLen就已经不一样了。 ----》 需要加上break语句。