84. Largest Rectangle in Histogram

Problem:

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

5/30/2018 update:
The stack only pops out which ever is shorter than current height. 
Why do we calc width from stack.peek instead of using the position of current height?
For instance, the above histogram. When reach end, the stack contains [3,2,1], when 2 is being popped. The actual width is from pos 2 to 5. 1 is stack top.  -------------------------------------------------------------------------------------------------------------------------------------------------------------------

Analysis:

Detailed illustration from here http://www.cnblogs.com/lichen782/p/leetcode_Largest_Rectangle_in_Histogram.html

Solution:

Start and i are both exclusive. 

class Solution {
    public int largestRectangleArea(int[] heights) {
        if (heights == null || heights.length == 0) return 0;
        Stack<Integer> stack = new Stack<>();
        int res = 0;
        for (int i = 0; i <= heights.length; i++) {
            int h = i == heights.length ? 0 : heights[i];
            while (!stack.isEmpty() && h < heights[stack.peek()]) {
                int height = heights[stack.pop()];
                int start = stack.isEmpty() ? -1 : stack.peek();
                res = Math.max(res, height * (i - start - 1));
            }
            stack.push(i);
        }
        return res;
    }
}