Maximal Rectangle -interesting

three methods are provided.

//first, using largestRectangleArea

    int maximalRectangle(vector<vector<char> > &matrix) {
        if (matrix.empty() || matrix[0].empty()) return 0;
        int N=matrix.size();
        int M=matrix[0].size();
        int ret=0;
        vector<int> height(M+1,0);
        for(int i=0;i<N;i++){
            for(int j=0;j<M;j++)
                height[j]=matrix[i][j]=='0'?0:height[j]+1;
            ret=max(ret,largestRectangleArea(height));   
        }
        return ret;   
    }
    int largestRectangleArea(const vector<int>& height){
        int N=height.size();
        int i=0;
        int ret=0;
        stack<int> stk;
        while(i<N){
            if(stk.empty()||height[stk.top()]<=height[i])
                stk.push(i++);
            else{
                int index=stk.top();stk.pop();
                int width=stk.empty()?i:i-(stk.top()+1);
                ret=max(ret,width*height[index]);
            }   
        }
        return ret;
    }

//second
    int maximalRectangle(vector<vector<char> > &matrix) {
        int num_i=matrix.size();
        if (num_i==0) return 0;
        int num_j=matrix[0].size();
        if (num_j==0) return 0;
        vector<vector<int>> max_x(num_i,vector<int>(num_j,0));  //number of consecutive 1s to the left of matrix[i][j], including itself

        int area=0;
        for (int i=0;i<num_i;i++){
            for (int j=0;j<num_j;j++){
                if (matrix[i][j]=='1'){
                    if (j==0) max_x[i][j]=1;
                    else max_x[i][j]=max_x[i][j-1]+1;
                    int y=1;
                    int x=num_j;
                    while((i-y+1>=0)&&(matrix[i-y+1][j]=='1')){
                        x=min(x, max_x[i-y+1][j]);
                        area=max(area,x*y);
                        y++;
                    }
                }
            }
        }

        return area;
    }

//third, most efficient, but a little hard to understand

http://hi.baidu.com/mzry1992/item/030f9740e0475ef7dc0f6cba

Case 1 -- matrix(i, j) = 1
H(i, j) = H(i-1, j) + 1
L(i, j) = max( L(i-1, j), the position of the left  nearest 0 in this row )
R(i, j) = min( R(i-1, j), the position of the right nearest 0 in this row )

Case 2 -- matrix(i, j) = 0
H(i, j) = 0
L(i, j) = 0
R(i, j) = n

 //
    int maximalRectangle(vector<vector<char> > &matrix) {
        if (matrix.empty()) {
            return 0;
        }

        int n = matrix[0].size();
        vector<int> H(n);
        vector<int> L(n);
        vector<int> R(n, n);

        int ret = 0;
        for (int i = 0; i < matrix.size(); ++i) {
            int left = 0, right = n;
            // calculate L(i, j) from left to right
            for (int j = 0; j < n; ++j) {
                if (matrix[i][j] == '1') {
                    ++H[j];
                    L[j] = max(L[j], left);
                }
                else {
                    left = j+1;
                    H[j] = 0; L[j] = 0; R[j] = n;
                }
            }
            // calculate R(i, j) from right to right
            for (int j = n-1; j >= 0; --j) {
                if (matrix[i][j] == '1') {
                    R[j] = min(R[j], right);
                    ret = max(ret, H[j]*(R[j]-L[j]));
                }
                else {
                    right = j;
                }
            }
        }

        return ret;
    }