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 height = [2,1,5,6,2,3],
return 10.
这题有两个解法，一个暴力O(n^2) 另一个是非常流弊聪明的O(n)，两个都花了我很长时间去思考，最后看了这篇博文 才略有所得。
首先暴破在现在看来思路应该是很直观的，但是我当时还是一点头绪没有，故思考良久以后决定去找答案。先来看看暴力法。
min_h = 0
max_a = 0 for i = [0 len){
if (min_h > height[i]) then continue
min_h = height[i]
for j = [i len){
if (min_h > height[j]){
min_h = height[j]
}
max_a = max(max_a, min_h * (j-i+1))
}
}
这是表达思路的伪码，大概就是，以每个柱子为基点，向前依次遍历其余柱子，用当前最短的那根乘上此刻前进的距离来求得面积，同时更新最大面积。这样遍历下来是O(n^2)的，虽然没有遗漏，但是也有很多不必要的枚举。
代码中 if (min_h > height[i]) then continue 这句是我尝试的一个优化，因为如果此趟遍历的高度都不超过前一趟的最小高度的话，这一趟得到的最大面积绝不会比前一趟大。但是这个优化仍是收效甚微，大集合没有通过。
至此也没有想到其他的优化手段，但是确实有人用优化过的暴力方法通过了大集合测试...我战斗力还是没有突破5啊。
暴力完整代码（Time Limit Exeeded）:
int largestRectangleArea(vector<int>height){
int maxArea=, minHeight=;
for (int i=; i<height.size(); i++){
if(height[i] <= minHeight)continue;
minHeight = height[i];
for (int j=i; j<height.size(); j++){
if (height[j] < minHeight){
minHeight = height[j];
}
int curArea = (j-i+) * minHeight;
if (curArea > maxArea){
maxArea = curArea;
}
}
}
return maxArea;
}
下面看看那个非常聪明流弊的O(n)解，还是建议去看一下开头提到的那篇博客，虽然几个图画的有问题，但是不影响理解的。
首先，他用一个栈来维护一个单调递增序列。 即在遍历过程中，遇到比栈顶大的才push。注意栈里保存的是索引。
如果遇到比栈顶小的，pop出栈顶并以他对应的实际数据为height，乘以一个width，求得面积并更新最大面积。那个width就是当前遍历位置i到当前栈顶（注意已经pop过一次）的间距(不包括当前栈顶位置)
这样到遍历完成的时候我们就可以得到最大面积，因为每次弹栈，我们都确保了弹出的那个家伙获得了他组成的最大面积。噢，为了确保最后把栈弹空，我们需要在原数据后面加一个dummy的0。
这是AC的：
int largestRectangleArea2(vector<int>height){
stack<int> s;
int maxArea = ;
int i=;
height.push_back();//dummy
int len = height.size();
while (i < len){
if (s.empty() || height[s.top()] < height[i]){
s.push(i++);
}else {
int h = s.top();
s.pop();
maxArea = max(maxArea, s.empty()? i*height[h] : height[h] * (i - s.top() - ));
}
}
return maxArea;
}