Largest Rectangle in Histogram

Problem

You are given an array heights of non-negative integers describing a histogram: bar i has height heights[i] and width 1, and bars are adjacent. Return the area of the largest axis-aligned rectangle that fits entirely inside the histogram (it may span several consecutive bars, and its height is limited by the shortest bar it covers).

• The histogram has between 1 and 150,000 bars.
• Each height is an integer between 0 and 50,000.

Examples

• heights = [3, 1, 4, 4, 6, 2] → 12. Height 4 across the three bars at indices 2, 3, 4 (heights 4, 4, 6) gives 4 * 3 = 12; the single bar of height 6 gives only 6.
• heights = [5, 3] → 6. Height 3 across both bars beats the lone bar of height 5.
• heights = [7, 7, 7, 7] → 28. One flat rectangle across all four bars.

Hints

1. Every maximal rectangle is exactly as tall as some bar i; it then extends left and right as far as the bars stay at least as tall as heights[i].
2. So for each bar you need the nearest shorter bar on the left and on the right. That is a "next smaller element" query.
3. A stack of indices with non-decreasing heights answers both boundaries as bars are popped. Append a sentinel 0 height to flush the stack at the end.