Largest Rectangle in Histogram

The problem. Given an array heights where each value is the height of a bar of width 1 in a histogram, return the area of the largest rectangle that fits entirely inside the histogram.

Example

Input:  heights = [2, 1, 5, 6, 2, 3]    Output: 10
Input:  heights = [2, 4]                Output: 4
Input:  heights = [6, 2, 5, 4, 5, 1, 6] Output: 12   (height 4 across 5, 4, 5)

A rectangle's height is limited by the shortest bar it covers. Flip that around: for every bar, imagine the rectangle that uses exactly that bar's height — it can stretch left and right until it hits a shorter bar. The answer is the best of these n rectangles.