083. Largest Rectangle in Histogram

 _           _
| |  _   _  | |
| | | |_| | | |
| | |*|*|*| | |
| |_|*|*|*| | |
| | |*|*|*|_| |
|_|_|_|_|_|_|_|
 6 2 5 4 5 1 6
     ^ ^ ^
 0 1 2 3 4 5 6

如图所示，很直观：3 * 4 == 12.首先思考，我们是如何得到最大面积 12 的？

我们发现，要计算 Largest Rectangle ，关键是找短板，如我们挑选的 4，类似的还有哪些呢？列个表：

min_height	rectangle	area
2	0 -> 4	2*5
4	2 -> 4	4*3
1	0 -> 6	1*6

最终很明显，area 最大的即为中间那行，结果为 12.

再进一步思考：

1. 短板是如何摘出来的？这个很显然，是衰减发生的时候出现的。如 6->2, 5->4, 5->1.
2. 短板的周期如何得出？细致观察后，发现是短板之间的升降分割出的。如 2->4:(2), 2->1, 4->1:(4), 2 和 4 便是分隔符。

好了，现在发现了规律，但如何准确找到所需的数据结构呢？

我们的第一个目的显然是要找出短板，短板的条件是：

height[i] < height[i-1]

貌似迭代一遍即可，但短板的周期分隔点如何得出呢？我们不仅要找出短板，还需要留下短板以及短板的 index, 以便寻找分隔符。

看来我们需要一把筛子，筛掉不符合短板条件的，留下短板。

栈非常符合筛子的特性，不管三七二十一，push 进去，不符合则 pop 出来。

int max_area = 0, i = 0, size = height.size();
for (stack<int> stk; i<size || !stk.empty(); ) { // 这个的 for 循环在二叉树的题目里经常出现（DFS）
    if (stk.empty() || (i != size && height[stk.top()] <= height[i])) stk.push(i++); // 不是短板，则 push
    else {
        int tp = stk.top(); stk.pop();
        max_area = std::max(max_area, height[tp] * (stk.empty() ? i : i-stk.top()-1));
    }
}

基本逻辑很简单，5 行结束。