Largest Rectangle Area Using Consecutive Histogram Bars
You are given a histogram represented by a list of non-negative bar heights. Every bar has a width of 1.
Find the largest rectangular area that can be formed using one or more consecutive bars. The rectangle's height is limited by the shortest bar it covers.
Method Signature
int largestRectangleArea(List<Integer> heights)
Parameters
heights contains the heights of the histogram bars from left to right.- Each bar has a width of
1.
Return Value
Return the area of the largest rectangle that can be formed in the histogram.
Constraints
1 <= heights.size() <= 100,0000 <= heights.get(i) <= 10,0000 <= i < heights.size()
Examples
Example 1
largestRectangleArea(heights = List.of(3, 1, 3, 2, 2))
Output: 6
The final three bars have a minimum height of 2, so they form a rectangle with area 2 * 3 = 6.
Example 2
largestRectangleArea(heights = List.of(4, 4, 1, 2))
Output: 8
The first two bars form a rectangle with height 4 and width 2.
Example 3
largestRectangleArea(heights = List.of(0, 2, 0, 3, 3, 3))
Output: 9
The final three bars form a rectangle with height 3 and width 3.
Example 4
largestRectangleArea(heights = List.of(5))
Output: 5
The only bar forms a rectangle with area 5.