Largest Rectangle in Histogram

A histogram has n bars of width 1 and heights h[i]. Find the area of the largest rectangle that fits entirely inside the histogram.

Input:

• line 1: n
• line 2: n heights

Output: the largest area (it can need a 64-bit integer).

Constraints: 1 ≤ n ≤ 10⁵, 0 ≤ h[i] ≤ 10⁴.

Think about it: for each bar, the best rectangle using that bar's full height stretches left and right until a shorter bar. A monotonic increasing stack finds both boundaries for every bar in one O(n) pass.