402. Largest Rectangle in Histogram (Stack)

Given a list of bar heights representing a histogram (each bar width 1), return the area of the largest rectangle that fits entirely under the histogram. A monotonic stack tracks candidate left boundaries. The heights are given as an array.

Input: An array of non-negative heights.

Output: Integer — the largest rectangle area.

Examples

Input: [2,1,5,6,2,3]
Output: 10
Explanation: Bars 5 and 6 give 2*5=10.

Input: [2,4]
Output: 4
Explanation: Bar of height 4.

Input: [1]
Output: 1
Explanation: Single bar.

Constraints

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

Asked by