欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

Largest Rectangle in Histogram

程序员文章站 2022-06-17 22:50:17
...

题目
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;
    }