Histogram Largest Rectangle via Monotonic Stack

Problem

Find the area of the largest rectangle that fits inside a histogram.

heights[i] is the bar height at position i and every bar has width 1. Use a monotonic increasing stack of indices; for each popped bar the rectangle extends to the previous smaller bar on the left and the current smaller bar on the right.

Return the maximum area (0 for an empty histogram).

Hint

Appending a zero height forces every remaining bar to be popped and evaluated.

Test cases

case 1

in: [[2,1,5,6,2,3]]

expected: 10

case 2

in: [[2,4]]

expected: 4

case 3

in: [[]]

expected: 0

case 4

in: [[5]]

expected: 5

case 5

in: [[3,3,3,3]]

expected: 12

Starter codePython

def largest_rectangle(heights):
    # Your code here
    pass

5 test cases · run your code against them in the editor