Problem. heights[i] is the height of bar i in a histogram where every bar has width 1. Return the area of the
largest rectangle that fits entirely under the bars.
heights = [2, 1, 5, 6, 2, 3] → 10 (height 5 across bars 2 and 3)
heights = [2, 4] → 4
heights = [3, 3, 3] → 9
A rectangle spanning bars l..r can be at most as tall as the shortest bar in that range: area =
min(heights[l..r]) × (r − l + 1). That's the whole problem; the work is avoiding every (l, r) pair.
ML context. Picture a timeline of free GPU memory, one bar per minute. A job that needs m GB for d minutes fits exactly when there's a window of d minutes where every bar is ≥ m: a rectangle under the histogram. The largest rectangle is the biggest job (in GB-minutes) the gap can hold, and the same stack answers "the longest window for a job that needs m GB" for every m at once (Change B).