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.

思路：

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

参考资料：http://www.cnblogs.com/lichen782/p/leetcode_maximal_rectangle.html

代码：

 1     int maxRectangleInHistogram(vector<int> &height){
 2         stack<int> 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<vector<char> > &matrix) {
27         // IMPORTANT: Please reset any member data you declared, as
28         // 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<vector<int> > height(m, vector<int>(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                 else
42                     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     }