Largest Rectangle in Histogram

Problem Given an array of integers representing the heights of bars in a histogram, where every bar has width 1, find the area of the largest rectangle that fits entirely within the histogram.

Input / Output

• Input: array heights of non-negative integers.
• Output: the maximum rectangle area as an integer.

Constraints

• Length up to 10^5, so an O(n^2) pairwise scan is too slow.
• Heights are >= 0; a zero-height bar splits the histogram.
• The area can overflow 32-bit arithmetic at the limits — use 64-bit.

Example

• heights = [2,1,5,6,2,3] → 10, from bars 5 and 6 spanning width 2 at height 5.
• Tricky: [2,1,2] → 3, height 1 across all three bars — the best rectangle need not include the tallest bar. A strictly increasing input [1,2,3,4,5] → 9 forces the stack to unwind at the end.