[LeetCode] Problem 84 - Largest Rectangle in Histogram

Posted on | In ,

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.

VaTo7Q.png

Above is a histogram where width of each bar is 1, given height = [2,1,5,6,2,3].

VaTLpq.png

The largest rectangle is shown in the shaded area, which has area = 10 unit.

Example

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

Output: 10

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public int largestRectangleArea(int[] heights) {
    int result = 0;
    Stack<Integer> stack = new Stack<>();

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

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

        stack.push(i);
    }

    return result;
}