Given an array of integers bar_heights representing the heights of bars in a histogram, where each bar has a width of 1, compute and return the maximum area of any rectangle that can be formed within the histogram. The rectangle must be fully contained within the histogram and can span multiple consecutive bars.
Example 1
Input: [3, 1, 3, 2, 2]
Output: 6
Explanation: The largest rectangle has area 6 (bars 3,2,2).
Example 2
Input: [1, 2, 3, 4, 5]
Output: 9
Explanation: The largest rectangle has area 9 (bars 3,4,5).
Example 3
Input: [5, 4, 3, 2, 1]
Output: 9
Explanation: The largest rectangle has area 9 (bars 5,4).
Constraints
Case 1
Input: [4, 2, 0, 3, 3]
Expected: 6
Case 2
Input: [2, 2, 2, 2, 2]
Expected: 10
Case 3
Input: [6, 2, 5, 4, 5, 1, 6]
Expected: 12
Case 4
Input: [1]
Expected: 1
Case 5
Input: [0, 0, 0, 0]
Expected: 0