Largest Rectangle in Histogram

Hard· monotonic stack· previous/next smaller

Problem

A histogram is given as an array of bar heights, each bar one unit wide. Return the area of the largest axis-aligned rectangle that fits entirely inside the histogram.

Examples

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

Output: 10

The bars of height 5 and 6 support a 5 x 2 rectangle.

Input: heights = [2,4]

Output: 4

Constraints

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

Hints & approach

Hint 1

The best rectangle is limited by its shortest bar. Try each bar as that shortest bar.

Hint 2

A bar can stretch left and right until it meets a shorter bar on each side.

Hint 3

An increasing stack of indices tells you both boundaries the moment a bar is popped.

Approachtry the hints first

Scan the bars, with a sentinel height 0 appended, keeping a stack of indices whose heights increase. When the current bar is shorter than the top, pop the top: its height is h, its right boundary is the current index, and its left boundary is the new stack top (or -1 if empty). The width is i - left - 1, so update the best area with h * width. Then push the current index. Each index is pushed and popped once, so the scan is linear.

Time O(n) · Space O(n)

← PreviousSum of Subarray Minimums DoneBack to Monotonic stack