Largest Billboard in a Skyline

Hardmonotonic stack 00:00

Building heights form a histogram (width 1 each). Return the area of the largest rectangle that fits entirely inside it.

largestRectangle(heights: int[]) → int

Example 1

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

output = 10

5 and 6 → height 5 × width 2 = 10

Example 2

heights = [2,4]

output = 4

⌘/Ctrl + Enter runs examples

Run checks the examples. Submit runs every hidden test (17, including large inputs that catch slow solutions).