84. Largest Rectangle in Histogram (Hard)

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.

For example,
Given heights =[2,1,5,6,2,3],
return10.

Solution 1: Stack O(n); O(n)

维护一个栈，用来保存递增序列，相当于上面那种方法的找局部峰值，当当前值小于栈顶值时，取出栈顶元素，然后计算当前矩形面积，然后再对比当前值和新的栈顶值大小，若还是栈顶值大，则再取出栈顶，算此时共同矩形区域面积，照此类推，可得最大矩形。

    public static int largestRectangleArea(int[] histogram) {
        int len = histogram.length;
        Stack<Integer> stack = new Stack<>();
        int maxArea = 0;
        for (int i = 0; i <= len; i++){ //notice =
            int height = i == len ? 0 : histogram[i];
            // 如果有新的高度，push到stack上去
            if (stack.isEmpty() || height >= histogram[stack.peek()]){
                stack.push(i);
            } else {
                // 没有遇见更高的高度，说明找到右边短边，这时候pop出来做计算
                int top = stack.pop();
                maxArea = Math.max(maxArea, histogram[top] * (stack.isEmpty() ? i : i - 1 - stack.peek()));
                i--; // 从右边最短边开始计算，利用右边最短边i与stack.peek()一直计算到最左边，来算面积
            }
        }
        return maxArea;
    }