Largest Rectangle in Histogram
Given an array of integers heights representing the histogram's bar height where the width of each bar is 1, return the area of the largest rectangle in the histogram.
Example 1
#
# #
# #
# # #
# # # # #
# # # # # #
2 1 5 6 2 3Input
heights = [2,1,5,6,2,3]Output
10The largest rectangle has height 5 and width 2, covering bars with heights 5 and 6 for an area of 10.
Example 2
# # # # # # 2 4
Input
heights = [2,4]Output
4The largest rectangle can use either the single bar of height 4 or both bars with height limited to 2, so the maximum area is 4.
Constraints
- 1 <= heights.length <= 10^5
- 0 <= heights[i] <= 10^4