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 =

return

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; } };

Excuse for my little Ads.

ReplyDeleteRather then this O(n*n), a O(n) algorithm can be found here

http://fmarss.blogspot.com/2014/08/leetcode-solution-largest-rectangle-in.html