Largest Rectangle in a Bar Chart

A bar chart has bars of width 1 standing side by side, with heights given by the list heights. Write largest_rectangle(heights) that returns the area of the largest rectangle that fits entirely inside the bars.

The rectangle stands on the ground with its sides along the grid lines. It can stretch across several neighbouring bars as long as it is no taller than the shortest of them.

Examples

largest_rectangle([2, 4, 4, 1, 3, 3, 3])  # returns 9
largest_rectangle([5])                    # returns 5
largest_rectangle([1, 1, 1, 1])           # returns 4
largest_rectangle([])                     # returns 0

In the first example the three bars of height 3 hold a 3 by 3 rectangle with area 9. That beats the 4 by 2 rectangle over the two bars of height 4 (area 8) and the 1 by 7 strip along the bottom (area 7).

Constraints

• 0 <= len(heights) <= 100,000
• 0 <= heights[i] <= 10,000
• Trying every pair of left and right edges is too slow for the largest charts.