LargestRectangleUnderHistogram.java

import java.util.*;
import org.junit.jupiter.api.*;

public class LargestRectangleUnderHistogram {

    public static int largestRectangleArea(int[] heights) {
        if (heights.length < 1) return 0;

        int maxArea = 0;
        Deque<Integer> stack = new ArrayDeque<>(heights.length);
        for (int i = 0; i < heights.length; ++i) {
            int h = heights[i];
            maxArea = Math.max(maxArea, h);

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

        while (!stack.isEmpty()) {
            int low = stack.pop();
            int len = stack.isEmpty()? heights.length : heights.length - stack.peek() - 1;
            maxArea = Math.max(maxArea, heights[low] * len);
        }

        return maxArea;
    }

    public static void main(String[] args) {
        Assertions.assertEquals(3, largestRectangleArea(new int[] {2,1,2}));
        Assertions.assertEquals(6, largestRectangleArea(new int[] {2,3,2}));
        Assertions.assertEquals(36, largestRectangleArea(new int[] {9,9,9,9}));
        Assertions.assertEquals(10, largestRectangleArea(new int[] {2,1,5,6,2,3}));
        Assertions.assertEquals(8, largestRectangleArea(new int[] {5,4,1,2}));
        Assertions.assertEquals(2, largestRectangleArea(new int[] {1,1}));
    }
}