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

Given height = [2,1,5,6,2,3],
return 10.

Solution: Maintain a increasing stack.

public int largestRectangleArea(int[] height) {
        // write your code here
        if(height == null || height.length == 0) {
            return 0;
        }
        int[] h = new int[height.length + 1];
        for(int i = 0; i < h.length - 1; i++) {
            h[i] = height[i];
        }
        int res = 0;
        Stack<Integer> stack = new Stack<Integer>();
        for(int i = 0; i < h.length; ) {
            if(stack.isEmpty() || h[i] > h[stack.peek()]) {
                stack.push(i++);
            }
            else {
                int len = stack.pop();
                res = Math.max(res, (stack.isEmpty() ? i : (i - stack.peek() - 1)) * h[len]);
            }
        }
        return res;
    }