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

思路：

该题可以看作Largest Rectangle in Histogram的变形，对于每行，求出一个height数组，然后求出可以得到的最大值。

参考资料：

代码：

1     int maxRectangleInHistogram(vector
     
       &height){ 2         stack
      
        Stack; 3         int i = 0, num = height.size(); 4         int result = 0; 5         while(i < num){ 6             if(Stack.empty() || height[Stack.top()] <= height[i]){ 7                 Stack.push(i++); 8             } 9             else{10                 int tmp = Stack.top();11                 Stack.pop();12                 int area = height[tmp]*(Stack.empty()?i:(i-Stack.top()-1));13                 if(area > result)14                     result = area;15             }16         }17         while(!Stack.empty()){18             int tmp = Stack.top();19             Stack.pop();20             int area = height[tmp]*(Stack.empty()?i:(i-Stack.top()-1));21             if(area > result)22                 result = area; 23         }24         return result;25     }26     int maximalRectangle(vector
       
        
          > &matrix) {27         // IMPORTANT: Please reset any member data you declared, as28         // the same Solution instance will be reused for each test case.29         int m = matrix.size();30         if(m == 0)31             return 0;32         int n = matrix[0].size();33         if(n == 0)34             return 0;35         vector
         
          
            > height(m, vector
           
            (n, 0));36 int i,j;37 for(i = 0; i < m; i++){38 for(j = 0; j < n; j++){39 if(matrix[i][j] == '0')40 height[i][j] = 0;41 else42 height[i][j] = i==0 ? 1 : height[i-1][j]+1;43 }44 }45 int result = 0;46 for(i = 0; i < m; i++){47 int tmp = maxRectangleInHistogram(height[i]);48 if(tmp > result)49 result = tmp; 50 }51 return result;52 }