610. Largest Rectangle in Histogram

Given the heights of adjacent bars of equal width 1, return the area of the largest rectangle that fits entirely under the histogram outline. The input is JSON {heights}.

Input: JSON {heights}.

Output: Integer — the largest rectangle area.

Examples

Input: {"heights":[2,1,5,6,2,3]}
Output: 10
Explanation: Bars 5 and 6 form a 5x2 rectangle.

Input: {"heights":[2,4]}
Output: 4
Explanation: Bar 4 alone.

Input: {"heights":[0]}
Output: 0
Explanation: Zero height.

Constraints

• 1<=n<=10^5
• 0<=height

Asked by