Largest Rectangle in Histogram

Hard

Given an array heights of bar heights (each width 1), return the area of the largest rectangle that fits in the histogram.

Example 1

Input:  heights = [2,1,5,6,2,3]
Output: 10

Example 2

Input:  heights = [2,4]
Output: 4

Constraints

• 1 <= heights.length <= 10^5
• 0 <= heights[i] <= 10^4