You are given vector<int> heights, where each element gives the height of a unit-width bar in a histogram. Return the maximum area of any rectangle that can be contained entirely within the histogram.
def largestRectangleArea(heights: List[int]) -> int:...
As you work, explain the time complexity of your approach and why the selected data structure is appropriate.
Input: heights = [2, 1, 2]
Output:
3
The rectangle of height 1 spans all three bars, giving area 1 × 3 = 3.
heights = [2,3
The histogram has bar heights [2, 1, 2].
heights = [2, 1, 5, 6, 2, 3]
10 The bars of heights 5 and 6 support a rectangle of height 5 and width 2, so the largest area is 10.
Be prepared to discuss the Maximal Rectangle problem on a binary matrix, which extends this histogram operation one row at a time.
heights = [2,3
The histogram has bar heights [2, 1, 2].