84. 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.

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.

For example,
Given heights = [2,1,5,6,2,3],
return 10.

Solution:

The idea is for each value at index i, we look left and look right to find the first value smaller than itself.

If we find these two indices, we can calculate the maximum rectangle at this index value height.

We use an increasing stack to store the first left index.

If we find a value is smaller than the top of the stack, this value is the first smaller value from stack top's right.

Therefore, we have stack top's first smaller value from its left and right, thus we can calculate the maximum rectangle with stack top's height.

We also push a dummy index with value -1 after traverse the input, in order to pop out all remaining indices from the stack.

The time complexity is O(n) and the space complexity is O(n).



Code:

public class Solution {
    public int largestRectangleArea(int[] heights) {
        if (heights == null || heights.length == 0) {
            return 0;
        }
        Stack<Integer> stack = new Stack<>();
        int max = 0;
        for (int i = 0; i <= heights.length; i++) {
            int curr = i == heights.length ? -1 : heights[i];
            while (!stack.isEmpty() && curr <= heights[stack.peek()]) {
                int height = heights[stack.pop()];
                int width = stack.isEmpty() ? i : i - stack.peek() - 1;
                max = Math.max(max, height * width);
            }
            stack.push(i);
        }
        return max;
    }
}