【leetcode】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.

使用dpHeight[]数组来记录到第i行为止，第j个位置垂直连续包含多少个1（包括matrxi[i][j]）。如：

1 0 1 1 0

1 1 0 1 0

0 1 1 1 1

有如下结果：

第1行： dpHeight[] = {1, 0, 1, 1, 0}

第2行： dpHeight[] = {2, 1, 0, 2, 0}

第3行： dpHeight[] = {0, 2, 1, 3, 0}

对每个dpHeight求最大矩形面积，利用Largest Rectangle in Histogram里面的求解方法即可

 1 class Solution {
 2 public:
 3     int maximalRectangle(vector<vector<char> > &matrix) {
 4        
 5        
 6         int m=matrix.size();
 7         if(m==0) return 0;
 8         int n=matrix[0].size();
 9        
10         vector<int> dpHeight(n,0);
11        
12         int result=0;
13         for(int i=0;i<m;i++)
14         {
15             for(int j=0;j<n;j++)
16             {
17                 if(matrix[i][j]=='1') dpHeight[j]++;
18                 else dpHeight[j]=0;
19             }
20            
21             int tmp=lineMaximalRectangle(dpHeight);
22             if(tmp>result) result=tmp;
23         }
24        
25         return result;
26     }
27    
28     struct Node
29     {
30         int index;
31         int height;
32         Node(int i,int h):index(i),height(h){};
33     };
34    
35     int lineMaximalRectangle(vector<int> &dpHeight)
36     {
37        
38        
39         int len=dpHeight.size();
40         if(len==0) return 0;
41        
42         stack<Node> stk;
43         Node n(0,dpHeight[0]);
44         stk.push(n);
45        
46         int result=0;
47         for(int i=1;i<len;i++)
48         {
49             int height=dpHeight[i];
50            
51             if(height>=stk.top().height)
52             {
53                 stk.push(Node(i,height));
54             }
55             else
56             {
57                 int nodeIndex=i;
58                 while(!stk.empty()&&height<stk.top().height)
59                 {
60                     int tmp=(i-stk.top().index)*stk.top().height;
61                     if(tmp>result) result=tmp;
62                     nodeIndex=stk.top().index;
63                     stk.pop();
64                 }
65                 stk.push(Node(nodeIndex,height));
66             }
67         }
68         while(!stk.empty())
69         {
70             int index=stk.top().index;
71             int height=stk.top().height;
72             int tmp=(len-index)*height;
73             if(tmp>result) result=tmp;
74             stk.pop();
75         }
76        
77         return result;
78        
79     }
80 };