All problems

Largest Rectangle in Histogram

Hard · stack

The list heights describes a bar chart. The bars stand side by side with no gaps, every bar is one unit wide, and bar i is heights[i] units tall.

You want to cut a rectangle out of the chart. The rectangle must lie completely inside the bars, so it covers a run of one or more neighbouring bars, and its height can be no more than the shortest bar in that run. Return the area of the biggest rectangle you can cut out.

A bar of height 0 has no area, and no rectangle can reach across it. If every bar has height 0, return 0.

Examples

Example 1

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

Output: 10

The bars 5 and 6 are neighbours, so a rectangle 2 wide and 5 tall fits: area 10.

Example 2

Input: heights = [2, 4]

Output: 4

Either the 4 on its own (area 4), or both bars with height 2 (area 4).

Example 3

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

Output: 12

The four bars 2, 5, 4, 5 in the middle allow a rectangle 4 wide and 2 tall (area 8), but the bars 5, 4, 5 give one 3 wide and 4 tall, which is 12.

Constraints