Largest Rectangle in Histogram — Leetcode 84

Original problem link: https://leetcode.com/problems/largest-rectangle-in-histogram/description/

In this problem, we’re given an array of heights representing heights in a histogram. We’re asked to find the maximum area of a rectangle created by the bars in the histogram, assuming each bar has width 1.

This shares some similarity with the trapping rainwater problem, but instead of being limited by taller walls, we are limited by the shortest heights. Therefore, we can pop taller intermediate walls from the stack, and calculate the max area of the rectangles along the way. The key is to find the correct height and width to use on each step, since this changes depending on whether the stack is empty and whether the current height matches the popped height.

class Solution {
    public int largestRectangleArea(int[] heights) {
        LinkedList<Integer> stack = new LinkedList<>();
        int result = 0;

        for (int i = 0; i < heights.length; i++) {
            // we want to eliminate the consideration of all heights greater than or equal to the current height since those would be able to cover a rectangle with current width and height
            // we can think of smaller heights as "walls" that may block the creation of a new rectangle
            while (!stack.isEmpty() && heights[stack.peek()] >= heights[i]) {
                int h = stack.pop();
                if (stack.isEmpty()) {
                    // it means we can make a rectangle all the way to the beginning of the histogram
                    result = Math.max(result, heights[h] * i);
                } else {
                    // we need to see whether to include the current height or not. We can't include if the current height is smaller than the popped out height
                    if (heights[h] == heights[i]) {
                        result = Math.max(result, heights[h] * (i - stack.peek()));
                    } else {
                        result = Math.max(result, heights[h] * (i - stack.peek() - 1));
                    }
                }
            }
            stack.push(i);
        }

        while (!stack.isEmpty()) {
            // check rectangles created by the increasing sequence in stack at the end
            int index = stack.pop();
            int width = stack.isEmpty() ? heights.length : heights.length - stack.peek() - 1;
            result = Math.max(result, heights[index] * width);
        }

        return result; 
    }
}

This solution has a runtime of 21 ms and beats 92% of submissions in runtime.