leetcode Question 47: Maximal Rectangle

Maximal Rectangle
Given a 2D binary matrix filled with 0's and 1's, find the largest rectangle containing all ones and return its area.

Analysis:

This is not an easy problem and the idea is not straightforward.
Since the question requires the area of all ones region, first we can define the region (rectangle) in the matrix. Any region in the matrix has several basic properties:   1 corner point,  width, and length.
Also which corner point it is decide the exact place of the region, here we consider the bottom-right corner point, because we usually scan the matrix from (0,0) to right and down direction. For this problem, we also need to consider the "all ones" requirement, where all the regions are filled with 1s.

We can then have this data structure:
One 2D array(vector) ones[i][j],  where ones[i][j] stores the number of contiguous 1s ended at matrix[i][j], along ith row. e.g.  if matrix[i] = "1011101", then ones[i]=1,0,1,2,3,0,1. This array stores the length of the rectangle, for every possible bottom-right corner point.

Having this two values, next is to find the height of the rectangle, as well as keep the "all ones" requirement.
Start with a corner point [i][j],  since it is the bottom right corner, the rectangle search direction is left and up.
For the left we already have the number of contiguous 1s ones[i][j]. How to get the height?  We need to scan all the values above ones[i][j], it is from i-1 to 0. If meets 0, then stop, else compute the possible rectangle area, and store the max. To compute the area, the minimum length of rectangle should be compared and stores every time.

Details can be found in the code below, which passed all the small and big test cases.

Code(updated 201309):

class Solution {
public:
    int maximalRectangle(vector<vector<char> > &matrix) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int row = matrix.size();
        if (row==0){return 0;}
        int col = matrix[0].size();
        int res=0;
        vector<vector<int>> ones(row,vector<int>(col,0));
            
        for (int i=0;i<row;i++){
            for(int j=0;j<col;j++){
                if (matrix[i][j]=='1'){  
                    if (j==0){ones[i][j]=1;}
                    else{ones[i][j]=ones[i][j-1]+1;}
                }
            }
        }
        
        for (int i=0;i<row;i++){
            for(int j=0;j<col;j++){
                if (ones[i][j]!=0){  
                    int h = i-1;
                    int tmp=ones[i][j];
                    int mini=ones[i][j];
                    while (h>=0){
                        if (ones[h][j]==0){
                            break;
                        }else{
                            if (ones[h][j]<mini){
                                mini = ones[h][j];
                            }
                            if (tmp< mini*(i-h+1)){
                                tmp= mini*(i-h+1); 
                            }
                            h--;
                        }
                    }
                    if (res<tmp){
                        res=tmp;
                    }
                }
            }
        }
        
        return res;
    }
};