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.

答案

每次看到更高的height的时候，就把它放进stack里
遇到比stack.top()小的height时，则开始pop stack，计算rectangle的面积
直到iterate完整个heights数组，以及stack里也为空时则完成

    public int largestRectangleArea(int[] heights) {
        Stack<Integer> pos = new Stack<>();
        Stack<Integer> h = new Stack<>();

        int max_area = 0;
        for(int i = 0; i < heights.length; i++) {
            int curr_h = heights[i];
            if(h.empty() || curr_h > h.peek()) {
                h.push(curr_h);
                pos.push(i);
            }

            int last_h = h.peek();
            int last_pos = pos.peek();

            if(curr_h < last_h) {
                int idx = 0, hs = 0;
                while(!h.empty() && h.peek() > curr_h) {
                    idx = pos.pop();
                    hs = h.pop();
                    max_area = Math.max(max_area, hs * (i - idx));
                }
                h.push(curr_h);
                pos.push(idx);

            }
        }
        while(!h.empty()) {
            max_area = Math.max(max_area, h.pop() * (heights.length - pos.pop()));
        }
        return max_area;
    }