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.

tag: 单调栈

class Solution {
    public int largestRectangleArea(int[] heights) {
        Stack<Integer> stack = new Stack<>();

        int ans = 0;
        for (int i = 0; i <= heights.length; i++){
            int curH = i == heights.length ? -1 : heights[i];

            while (!stack.isEmpty() && curH < heights[stack.peek()]){
                int h = heights[stack.pop()];
                int w = stack.isEmpty() ? i : i - stack.peek() - 1;
                ans = Math.max(ans, h * w);

                //System.out.println("i: " + i + " h: " + h + " w: " + w);
            }
            stack.push(i);
        }

        return ans;
    }
}