Biggest Rectangle Under the Skyline

Hard

A city skyline is a row of towers of width 1 standing right next to each other. Their heights, from left to right, are given in the array towers. Fit an axis-aligned rectangle into the skyline so that it rests on the ground and lies entirely within the towers. Return the largest possible area of such a rectangle.

Example 1

towers=[3, 1, 4, 4, 2, 5] → 8

The two towers of height 4 stand side by side: a 4 × 2 rectangle has area 8. Height 2 across towers 2–5 also gives 8, and nothing beats that.

Example 2

towers=[2, 2, 2, 2] → 8

The whole row has the same height: 2 × 4 = 8.

Example 3

towers=[0, 6, 0] → 6

The zeros on both sides limit the width: 6 × 1 = 6.

Constraints

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

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Stack Array Monotonic Stack

Similar problems

Water Between Walls Hard Biggest Solid Panel Block Hard Largest Number From Two Rows Hard Sorting Batches With Repeats Hard Frog on the Posts Hard

Input

towers=[3, 1, 4, 4, 2, 5]

Expected

Run checks the first 3 tests in your browser. Submit checks all 99 tests on the server, hidden ones included.