84. Largest Rectangle in Histogram

Leetcode Array Stack

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 = 10 unit.

Example:

Input: [2,1,5,6,2,3]
Output: 10

分析

这道题目其实挺难的，一看到题目的时候根本不知道用什么好的解决方法。这里巧妙的利用的stack。stack里存放的是依次递增的数组。当数组依次递增的时候，当前的数字肯定不是右边界，所以不需要求最大面积，只需要依次入栈(stack.push(i))。当遇到递减的元素的时候(heights[stack.peek()] >= cur)，需要停下来求一下面积。首先找到右边界，既然这个数字是减小了的，那么右边界肯定不是它，而是前面的那个数字(i-1)。那么左边界呢？我们构造一个循环，依次弹出栈顶元素，如果它比当当前值要小，那肯定不是；否则依次求其面积(h * w)。

/**
 * find the area of largest rectangle in the histogram
 * @param heights: an array of non-negative integers
 * @return: the area of largest rectangle in the histogram
 */
public static int largestRectangleArea(int[] heights) {
    if (heights == null || heights.length == 0) {
        return 0;
    }
    Stack<Integer> stack = new Stack<Integer>();
    int ans = 0;
    for (int i = 0; i <= heights.length; i++) {
        int cur = (i == heights.length) ? -1 : heights[i];
        while (!stack.isEmpty() && heights[stack.peek()] >= cur) {
            int h = heights[stack.pop()];
            int w = stack.isEmpty() ? i : i - stack.peek() - 1;
            ans = Math.max(ans, h * w);
        }
        stack.push(i);
    }
    return ans;
}

reference: https://www.geeksforgeeks.org/largest-rectangle-under-histogram/