Largest Rectangle in Histogram LeetCode solution in Python

1
class Solution:
2
    def largestRectangleArea(self, heights: List[int]) -> int:
3
        maxArea = 0
4
        stack = []  # (index, height)
5

6
        for i, h in enumerate(heights):
7
            startIndex = i
8
            while stack and stack[-1][1] > h:
9
                index, height = stack.pop()
10
                maxArea = max(maxArea, height * (i - index))
11
                startIndex = index
12
            stack.append((startIndex, h))
13

14
        for index, height in stack:
15
            maxArea = max(maxArea, height * (len(heights) - index))
16

17
        return maxArea