Largest Rectangle in Histogram

You get a list heights. Each number is the height of a bar, and every bar is 1 unit wide. The bars stand side by side.

Return the biggest area a rectangle can have.

A rectangle covers one bar or several bars next to each other. It can be as tall as the shortest bar it covers.

Example 1:

Input: heights = [1,4,5,3,6,2]
Output: 12
Explanation: The best rectangle covers the bars 4, 5, 3 and 6.
It is 4 bars wide.
It is 3 tall, the height of the shortest of them.
Its area is 4 × 3 = 12.
The 4 and the 5 alone give only 2 × 4 = 8.

Example 2:

Input: heights = [5,0,4,4]
Output: 8
Explanation: The bar of height 0 splits the row in two.
The two 4s give 2 × 4 = 8.
The 5 alone gives only 5.

Example 3:

Input: heights = [7]
Output: 7

Constraints:

• 1 to 30,000 bars.
• Each height is a whole number from 0 to 10,000.