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 heights = [2,1,5,6,2,3],
return 10.
class Solution {
public:
int largestRectangleArea(vector<int>& heights) {
int n = heights.size();
if( == n)
return ;
int max = , area, i, k;
stack<int> s;
heights.push_back();
for(i = ; i <= n; i++)
{
if(s.empty() || heights[i] >= heights[s.top()])
{
s.push(i);
continue;
}
k = s.top();
s.pop();
area = heights[k] * ( == s.size() ? i : i - s.top() - );
if(area > max)
max = area;
i--;
}
return max;
}
};
维护一个栈，每个bar进栈一次，保持栈内元素递增，若新元素小于栈顶元素，则出栈计算面积。