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.
最开始的想法是寻找以每一根柱为起始的最大面积，时间复杂度为O(n^2)，超时了。
O(n)的做法见http://www.cnblogs.com/felixfang/p/3676193.html 主要思路是利用栈将直方图分解为递增段，而求解递增段的时间复杂度为O(n)。
inline int max(int a, int b) { return a>b ? a : b; } int largestRectangleArea(vector<int>& heights) { int s = 0; heights.push_back(0); stack<int> h; for (int i = 0; i<heights.size(); i++) { if (h.empty() || heights[h.top()]<heights[i]) h.push(i); else { int tmp = h.top(); h.pop(); if (h.empty()) s = max(s, heights[tmp] * i);//当栈为空，表示heights[tmp]比之前i个都小(栈底最小) else s = max(s, heights[tmp] * (i - h.top() - 1)); i--; } } return s; }
leetcode-84. Largest Rectangle in Histogram
原文：http://www.cnblogs.com/tonychen-tobeTopCoder/p/5183758.html