14. Largest Rectangle in Histogram

Hard · Array

Given an array of non-negative integers representing the heights of bars in a histogram, find the area of the largest rectangle that can be formed within the histogram.

A rectangle's width is determined by consecutive bars, and its height is limited by the shortest bar in that range. You must find the maximum area possible by considering all possible rectangles.

Examples

Example 1
Input: [2, 1, 5, 6, 2, 3]
Output: 10
Explanation: The largest rectangle has height 5 and width 2 (bars at indices 2 and 3), giving area 5 × 2 = 10.
Example 2
Input: [2, 4]
Output: 4
Explanation: The largest rectangle uses the bar of height 4 with width 1, giving area 4 × 1 = 4.

Constraints