Given an array of integers, heights, that represents the heights of bars in a histogram, find the area of the largest rectangle in the histogram, where the rectangle has a constant width of $1$ unit for each bar.

Constraints

• $1 \leq$ heights.length $\leq 10^3$
• $0 \leq$ heights[i] $\leq 10^4$

Let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem:

Implement your solution in the following coding playground.