Example: Largest Rectangle in Histogram

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

Given an array of integers heights representing the histogram's bar height where the width of each bar is 1, return the area of the largest rectangle in the histogram.

class Solution {
    // monotonic stack approach => O(n)
    public int largestRectangleArea(int[] heights) {
        int n = heights.length;
        // The stack stores the indices in non-decreasing order of heights.
        Stack<Integer> stack = new Stack<>();
        int maxArea = 0;      
        
        // iterate through each bar, including an additional bar of height 0 
        // at the end to ensure that all bars are processed.
        for (int i = 0; i <= n; i++) {
            int h = (i == n) ? 0 : heights[i];
            // If current bar's height is >= to stack top bar, push curr bar index
            while (!stack.isEmpty() && h < heights[stack.peek()]) {
                // found rectangle boundary, pop until bar <= curr
                int height = heights[stack.pop()];
                // For each popped index, calculate the area of the rectangle formed by 
                // considering the popped bar as the smallest bar. 
                // The width of the rectangle is determined by the difference 
                // between the current index and the index of the bar at the top of the stack. 
                // We update the maximum area accordingly.
                int width = stack.isEmpty() ? i : i - stack.peek() - 1;
                maxArea = Math.max (maxArea, height * width);
            }
            stack.push(i);
        }

        return maxArea;        
    }
}