Largest Rectangle in Histogram

Hard·Tagsarraystackmonotonic-stack

Problem Statement

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.

Examples

Example 1

Input

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

Histogram

Output

"10"

Why

The largest rectangle is formed by the bars at indices 2 and 3 (heights 5 and 6). Its height is limited by the shorter bar (5), and its width is 2. The area is 5 * 2 = 10.

Example 2

Input

heights: [2, 4]

Histogram

Output

"4"

Why

The largest rectangle can either be the single bar of height 4 (area 4) or both bars limited by height 2 (area 2 * 2 = 4). The maximum is 4.

Constraints

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

Hints

Stuck? Reveal a nudge toward the right pattern, one step at a time.

Hint 1

A rectangle is always restricted by the shortest bar within its span.

Hint 2

If we use a Monotonic Increasing Stack to store the indices of the bars, we can easily find the left and right boundaries for any given bar.

Hint 3

When you encounter a bar shorter than the bar at the top of the stack, it means the bar at the top of the stack cannot extend any further to the right. The current index is its right boundary!

Hint 4

What is the left boundary for the popped bar? It's the new top of the stack after popping. The width of the rectangle is `(right_boundary - left_boundary - 1)`.