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