[LeetCode] 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的时候有人说可以用在这题，看了一下还真是，以每行为x轴，每列往上累计的连续的1当成高度，就可以完全使用一样的方法了。

 1 int largestArea(vector<int>height){
 2     stack<int> s;
 3     int maxArea = 0;
 4     int i = 0;
 5     height.push_back(0);
 6     int len = height.size();
 7 
 8     while (i < len){
 9         if (s.empty() || height[s.top()] < height[i]){
10             s.push(i++);
11         }else{
12             int t = s.top();
13             s.pop();
14             maxArea = max(maxArea, height[t] * (s.empty()? i : (i-s.top()-1)));
15         }
16     }
17     return maxArea;
18 }
19 
20 int maximalRectangle(vector<vector<char>> &matrix){
21     vector<int> height;
22     int maxRect=0;
23     for (int row=0; row<matrix.size(); row++){
24         for (int col=0; col<matrix[row].size(); col++){
25             if (matrix[row][col] == '0'){
26                 height.push_back(0);
27             }
28             else{
29                 int c=0;
30                 for (int i=row; i>-1; i--){
31                     if (matrix[i][col] != '0'){
32                         c++;
33                     }else {
34                         break;
35                     }
36                 }
37                 height.push_back(c);
38             }
39         }
40         
41         for (int i=0;i<height.size(); i++){
42             cout << height[i] << " ";
43         }
44         cout << endl;
45         
46         maxRect = max(maxRect, largestArea(height));
47         height.clear();
48     }
49     return maxRect;
50 }
51 
52 
53 int maximalRectangle2(vector<vector<char>> &matrix){
54     int maxRect = 0;
55     if (matrix.size() < 1) return 0;
56     vector<int>height(matrix[0].size(), 0);
57     for (int i=0; i<matrix.size(); i++){
58         for (int j=0; j<matrix[i].size(); j++){
59             if (matrix[i][j] == '1'){
60                 height[j] += 1;
61             }else{
62                 height[j] = 0;
63             }
64         }
65         maxRect = max(maxRect, largestArea(height));
66     }
67     return maxRect;
68 }

第一个maximalRectangle函数我用了很蠢的遍历方法来获得每行的height，这样活生生的把原本O(n^2)搞成了O(n^3)。。。最后看了别人博客，说height是可以通过前一行的值算出了的(有点类似DP的思想...如果这也算的话)，豁然开朗，才写出了

maximalRectangle2这个真正的O(n^2)方法。