Maximal Square

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

A: 

思路参考 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语句。