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.

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 =10unit.

Example

Given height = [2,1,5,6,2,3],
return 10.

Solution

遍历的时候，如果后面一个高度比当前的高度矮，那当前的高度就不能cover到之后的index了。所以用一个递增的stack来储存height，遇到小的height就把高的height pop出来，顺便把pop出来的高的height能组成的最大方形面积计算了。
要注意的一点是，pop出来一个height的时候怎么计算这个height能够cover到的最大width。往右它能cover到这个height到遍历的当前点之间的所有index，往左它能cover到这个height对应的点到stack中在它前面的那个比它小的height对应的index，所以width = cur index - stack.peek() - 1，当stack前面没有点的时候，说明这个height能一直cover到index = 0的点，那么往左能cover的最小index记作-1。

public class Solution {
    /*
     * @param height: A list of integer
     * @return: The area of largest rectangle in the histogram
     */
    public int largestRectangleArea(int[] height) {
        // write your code here
        if (height == null || height.length == 0) {
            return 0;
        }

        Stack<Integer> stack = new Stack<Integer>();
        int max = 0;
        for (int i = 0; i <= height.length; i++) {
            int curH = i == height.length ? 0 : height[i];
            while (!stack.isEmpty() && height[stack.peek()] >= curH) {
                int h = height[stack.pop()];
                int index = stack.isEmpty() ? -1 : stack.peek();
                int width = i - index - 1;
                max = Math.max(max, h * width);
            }

            stack.push(i);
        }

        return max;
    }
}