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.

Have you met this question in a real interview?

Yes

Example

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

思路：

1.如果是暴力枚举可以枚举左，右边界，或者枚举高。

1. 如果我们枚举高的话，我们需要知道，一个柱子左边第一个比它小的，和右边第一个比它大的。

2. 这个信息可以用单调栈来维护 （注意是存下标）

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> monStack = new Stack<Integer>();
        int ans = 0;
        //if we enumerate the height, then we need to know what is the index of the first left position that has a polar shorter than current point
        //and what is the index of the first right position that has a polar higher than current point
        monStack.push(-1);
        monStack.push(0);
        for (int i = 1; i <= height.length; i++) {
            int right = 0;
            int rightIndex = i;
            if (i < height.length) {
                right = height[i];
            }
            while (monStack.peek() != -1 && right <= height[monStack.peek()]) {
                int curIndex = monStack.pop();
                int curHeight = height[curIndex];
                int width = i; // to only itself
                // while (monStack.peek() != -1 && height[monStack.peek()] == curHeight) {
                //     width++;
                //     monStack.pop();
                // }
                if (monStack.peek() != -1) {
                    width = i - monStack.peek() - 1;
                }

                //System.out.print(curHeight + "," + width);
                //System.out.println("");
                ans = Math.max(ans, curHeight * width);
            }
            monStack.push(rightIndex);
        }

        return ans;
    }
}