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.

 

Example:

Input: [2,1,5,6,2,3]
Output: 10

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        int ans=0;
        heights.push_back(0);
        int n=heights.size();
        if(n==0)
            return 0;
        if(n==1)
            return heights[0];

        
        stack<int> s;
        for(int i=0;i<n;++i)
        {
            while(!s.empty()&&heights[s.top()]>=heights[i])
            {
                int h=heights[s.top()];
                s.pop();
                int l=s.empty()?-1:s.top();
                ans=max(ans,(i-l-1)*h);
                
            }
            s.push(i);
        }
        return ans;
    }
};