Largest Rectangle in Histogram

hard

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.

Test Cases

Copy an input into the main harness and Run to verify

Input

heights = [2,1,5,6,2,3]

Expected Output

10

Explanation: The largest rectangle spans bars of height 5 and 6, area = 2 * 5 = 10.

Input

heights = [2,4]

Expected Output

4

Constraints

1 <= heights.length <= 10^5
0 <= heights[i] <= 10^4

Hints

Hint 1 — click to reveal

For each bar, find how far left and right it can extend: until a shorter bar appears.

Hint 2 — click to reveal

A monotonically increasing stack resolves these boundaries in one pass.

Java Compiler