Largest Rectangle in Histogram

Given n non-negative integers representing the histogram’s bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.

Above is a histogram where width of each bar is 1, given height = [2,1,5,6,2,3].

C++:
01 class Solution {
02 public:
03     int largestRectangleArea(vector<int> &height) {
04         // Start typing your C/C++ solution below
05         // DO NOT write int main() function
06         int n=height.size();
07         if(n==0)
08             return 0;
09         stack<int> H;
10         stack<int> I;
11         int result=0;
12         int prvIndex=0;
13         for(int i=0;i<n;i++)
14         {
15             int p=height[i];
16             if(H.empty())
17             {
18                 H.push(p);
19                 I.push(i);
20                 continue;
21             }
22             int q=H.top();
23             if(p==q)
24                 continue;
25             if(p>q)
26             {
27                 H.push(p);
28                 I.push(i);
29                 continue;
30             }
31             while((!H.empty())&&(H.top()>p))
32             {
33                 int q=H.top();
34                 int index=I.top();
35                 int tmp=(iindex)*q;
36                 result=result>tmp?result:tmp;
37                 prvIndex=I.top();
38                 H.pop();
39                 I.pop();
40             }
41             H.push(p);
42             I.push(prvIndex);
43           }
44           while(!H.empty())
45           {
46               int h=H.top();
47               int w=nI.top();
48               int tmp=h*w;
49               result=result>tmp?result:tmp;
50               H.pop();
51               I.pop();
52           }
53           return result;
54     }
55 };
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