Leetcode: Largest Rectangle in Histogram

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.

Solution:

最容易和直接的解法是穷举法，对于直方图的每一个右边界，穷举所有的左边界。将面积最大的那个值记录下来。时间复杂度为O(n^2). 单纯的穷举在LeetCode上面过大集合时会超时。

优化解法：选择合适的右边界，skip没有意义的右边界。观察发现当height[k+1] >= height[k]时，无论左边界是什么值，选择height[k+1]总会比选择height[k]所形成的面积大。因此，在选择右边界的时候，首先找到一个height[k] > height[k+1 ]，然后取k 作为右边界，穷举所有左边界，找最大面积。值得注意的一点是一些特殊情况 such as 所有直方图是升序。此解法可以通过leetcode all test cases.

最后一个解法，时间复杂度为O(n)，利用一个stack存储高度递增的下标。这个方法的核心是：不仅选择合适的右边界，同时也选择合适的左边界，skip不必要的边界选择
对于每一个直方图高度，分两种情况。1：当栈空或者当前高度大于栈顶下标所指示的高度时，当前下标入栈。否则，2：当前栈顶出栈，并且用这个下标所指示的高度计算面积。而这个方法为什么只需要一个栈呢？因为当第二种情况时，for循环的循环下标回退，也就让下一次for循环比较当前高度与新的栈顶下标所指示的高度，注意此时的栈顶已经改变由于之前的出栈。

还有一个注意的点就是 width = stack.empty() ? i : i - stack.peek() - 1

Reference: http://blog.csdn.net/abcbc/article/details/8943485
                  http://www.geeksforgeeks.org/largest-rectangle-under-histogram/