Find the area of the largest axis-aligned rectangle that can be formed using adjacent histogram bars.
Given an array of non-negative integers representing the heights of bars in a histogram, determine the maximum area of a rectangle that can be formed by choosing one or more consecutive bars. The rectangle must be fully contained within the histogram, and its height is limited by the shortest bar in the chosen range.
Your task is to return the area of the largest such rectangle.
Input Format
- An integer array
heights, whereheights[i]is the height of thei-th bar. - Bars are placed side by side with unit width.
Output Format
- Return a single integer: the maximum rectangle area that can be formed from consecutive bars.
Constraints
1 <= heights.length.heights[i] >= 0.- The answer fits within a 32-bit signed integer for standard interview settings.
Example 1
Input
heights = [2,1,5,6,2,3]
Output
10
Explanation
The largest rectangle uses the bars with heights 5 and 6, giving width 2 and height 5, so the area is 10.
Example 2
Input
heights = [2,4]
Output
4
Explanation
Either bar alone gives areas 2 and 4. The maximum is 4.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.