Givennnon-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.

public class Solution {
    public int largestRectangleArea(int[] heights) {
        // use stack store the index of single ascending subsequence(not necessary continuous)
        Deque<Integer> stack = new LinkedList<Integer>();
        if (heights == null || heights.length == 0) {
            return 0;
        }

        int largest = Integer.MIN_VALUE;
        for (int i = 0; i <= heights.length; i++) {
            int h = (i == heights.length ? -1 : heights[i]);
            if (stack.isEmpty() || h > heights[stack.peekFirst()] ) {
                stack.offerFirst(i);
            } else {
                int index = stack.pop();
                int area = heights[index] * (stack.isEmpty() ? i : i - 1 -stack.peekFirst());
                largest = Math.max(area,largest);
                i--;
            }
        }
        return largest;
    }
}