Rectangle Series Questions

84. Largest Rectangle in Histogram

https://leetcode.com/problems/largest-rectangle-in-histogram/description/ 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. For example, Given heights = [2,1,5,6,2,3], return 10.

Solution Solution 1: 中心开花。（在每一个点，向左，向右找左右极限边界，然后计算面积。） Solution 2: Stack Idea是 set up a stack。Stack存idx，是个单调递增的stack。因为是单调递增的，我们知道每一个点的height，左边界（该点弹出后peek()得到的idx ＋ 1）。此时，问题转化成，哪一个是右边界。右边界发生在，当新遇到的点的height小于stack.peek（）的高度，即右边界是curIdx － 1. 此时开始弹出stack中的点计算面积。

注意的地方

1. stack中要存的是idx。 需要比较的是heights[cur] >= hieghts[stack.peek()]
2. 考虑stack为空的情况
3. 当不断弹出，stack为空时，left边界应该是0.
4. 我们需要在最后加一个－1点，使右边缘的concer case得到考虑。