首页 > itarticle > [leetcode] problem 84 – largest rectangle in histogram

[leetcode] problem 84 – largest rectangle in histogram

admin 11月 13, 2020 0

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

Code

public int (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;
}