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.

C++:
01 class Solution {
02 public:
03     int maximalRectangle(vector<vector<char> > &matrix) {
04         // Start typing your C/C++ solution below
05         // DO NOT write int main() function
06         int m=matrix.size();
07         if(m==0)
08             return 0;
09         int n=matrix[0].size();
10         vector<int*> A(m);
11         for(int i=0;i<m;i++)
12         {
13             A[i]=new int[n];
14             int tmp=0;
15             for(int j=n1;j>=0;j)
16             {
17                 if(matrix[i][j]==‘0’)
18                 {
19                     tmp=0;
20                 }
21                 else
22                 {
23                     tmp++;
24                 }
25                 A[i][j]=tmp;
26             }
27         }
28         int result=0;
29         for(int i=0;i<n;i++)
30         {
31            stack<int> H;
32            stack<int> I;
33            int prvIndex=0;
34            for(int j=0;j<m;j++)
35            {
36                int p=A[j][i];
37                if(H.empty())
38                {
39                    H.push(p);
40                    I.push(j);
41                    continue;
42                }
43                int q=H.top();
44                if(p==q)
45                    continue;
46                if(p>q)
47                {
48                    H.push(p);
49                    I.push(j);
50                    continue;
51                }
52                while((!H.empty())&&(H.top()>p))
53                {
54                    int q=H.top();
55                    int index=I.top();
56                    int tmp=(jindex)*q;
57                    result=result>tmp?result:tmp;
58                    prvIndex=I.top();
59                    H.pop();
60                    I.pop();
61                }
62                H.push(p);
63                I.push(prvIndex);
64              }
65              while(!H.empty())
66              {
67                  int h=H.top();
68                  int w=mI.top();
69                  int tmp=h*w;
70                  result=result>tmp?result:tmp;
71                  H.pop();
72                  I.pop();
73              }
74         }
75         return result;
76     }
77 };
Advertisements
This entry was posted in Array and linked list, Stack and Queue. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s