### leetcode Question 40: Largest Rectangle in Histogram

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].
The largest rectangle is shown in the shaded area, which has area = 10 unit.
For example,
Given height = [2,1,5,6,2,3],
return 10.

Analysis:
A simple but time-consuming idea is scan every element find the left bound and right bound.

Source Code:

class Solution {
public:
int largestRectangleArea(vector<int> &height) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
if (height.empty()){return 0;}
vector<int>l(height.size(),0);
vector<int>r(height.size(),0);

for (int i = 0; i<height.size();i++){
int j=i;
while((j>0) && (height[i]<=height[j-1])){ j=l[j-1];}
l[i]=j;
}

for (int i = height.size()-1;i>=0;i--){
int j=i;
while( (j<height.size()-1) && (height[i]<=height[j+1])){ j=r[j+1];}
r[i]=j;
}

int maxa=0;
for (int i=0;i<l.size();i++){
maxa = max(maxa,((r[i]-l[i]+1)*height[i]));
}
return maxa;

}
};


#### 1 comment:

1. Excuse for my little Ads.
Rather then this O(n*n), a O(n) algorithm can be found here