#193HardStacks· Monotonic Stack and Histograms

Largest Billboard Under the Skyline

A city skyline is described by the heights of `n` neighbouring buildings, each exactly one metre wide, standing shoulder to shoulder. An advertiser wants to hang one rectangular billboard that is attached to the ground and does not stick out above any building it covers, so it can span several neighbouring buildings but its height is limited by the shortest of them. Return the area (in square metres) of the largest such rectangle.

Input format

`heights`: an array of non-negative integers, the building heights left to right.

Output format

An integer: the largest rectangle area that fits under the skyline.

Examples

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

Output: 10

The buildings of heights 5 and 6 are neighbours; a billboard of height 5 and width 2 has area 10, the largest possible.

Input: heights = [2, 4]

Output: 4

Either the building of height 4 alone (area 4) or both buildings at height 2 (area 4).

Input: heights = [0, 0, 0]

Output: 0

Every building has height 0, so no billboard has positive area.

Constraints

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

#monotonic-stack
#stack
#arrays
#histogram