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.
The largest rectangle is shown in the shaded area, which has area =10
unit.
For example,Given heights =[2,1,5,6,2,3],return10.
class Solution {
public:
int largestRectangleArea(vector<int>& heights) {
stack<int> s;
heights.push_back(0);
int result = 0;
for(int i=0;i<heights.size();)
{
if(s.empty()||heights[i]>heights[s.top()])
s.push(i++);
else
{
int temp = s.top();
s.pop();
result = max(result,heights[temp]*(s.empty() ? i:i-s.top()-1));
}
}
return result;
}
};
