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

Example

Input:
 [2,1,5,6,2,3]

Output:
 10

Note

单调栈严格递增栈，可以跑一下test case：

height	2	6	5	3	2	1
width	1	1=4-2-1	2=4-1-1	1=6-4-1	4=6-1-1	6
i	1	4	4	6	6	6
s.peek()	null	2	1	4	1	null
res	2	6	10	3	8	6

Code

class Solution {
    public int largestRectangleArea(int[] heights) {
        int res = 0;
        if (heights == null || heights.length == 0) {
            return res;
        }

        Stack<Integer> stack = new Stack<Integer>();    
        for (int i = 0; i <= heights.length; i++) {
            int h = (i == heights.length) ? -1 : heights[i];

            while (!stack.isEmpty() && h <= heights[stack.peek()]) {
                int height = heights[stack.pop()];
                int w = stack.isEmpty() ? i : i - stack.peek() - 1;
                System.out.println(height * w);
                res = Math.max(res, height * w);
            }
            stack.push(i);
        }

        return res; 
    }
}