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(0 == n) return 0; int max = 0, area, i, k; stack<int> s; heights.push_back(0); for(i = 0; i <= n; i++) { if(s.empty() || heights[i] >= heights[s.top()]) { s.push(i); continue; } k = s.top(); s.pop(); area = heights[k] * (0 == s.size() ? i : i - s.top() - 1); if(area > max) max = area; i--; } return max; } };
维护一个栈，每个bar进栈一次，保持栈内元素递增，若新元素小于栈顶元素，则出栈计算面积。
84. Largest Rectangle in Histogram *HARD* -- 求柱状图中的最大矩形面积
原文：http://www.cnblogs.com/argenbarbie/p/5804195.html