654. Largest Rectangle in Histogram (Optimal)

Given the bar heights of a histogram (each width 1), return the area of the largest rectangle that fits entirely within it, using an optimal O(n) stack method. 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 give 5x2.

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

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

Constraints

• 1<=n<=10^5

Asked by