Largest rectangle in a histogram

hardMonotonic stack target 40 min

Largest rectangle in a histogram

Not solved yetLeetCode 84. Largest Rectangle in Histogram

A histogram is a bar chart. This one has bars of width 1 standing side by side with no gaps, and heights[i] is the height of bar i. You want to draw a rectangle inside the chart. It stands on the ground, covers a run of neighboring bars, and is no taller than the shortest bar in that run.

Return the largest area such a rectangle can have, as an integer.

Example 1

Inputheights = [2, 4, 5, 1, 3]Output8

Cover the bars of height 4 and 5. The shorter one is 4, so the rectangle is 4 tall and 2 wide: 4 × 2 = 8.

Example 2

Inputheights = [2, 1, 2]Output3

Each 2 alone gives an area of 2. The 1 is short, but a rectangle 1 tall can cover all three bars, for an area of 3.

Example 3

Inputheights = [3, 3, 3]Output9

One rectangle 3 tall covers all three bars: 3 × 3 = 9.

Constraints

1 ≤ len(heights) ≤ 10⁵
0 ≤ heights[i] ≤ 10⁴

Plan it first

Write a line for each before you code, then say them out loud. Compare with the Approach tab afterwards.

Walk In what order will you visit the input?Notebook What will you write down as you go?Promise What stays true after every step?Cost Time and space, in Big O.

Run examples checks the examples. Submit runs every test, including edge cases and, when the problem has one, a speed check on a large input.

Same pattern