LeetCode 84 - Largest Rectangle in Histogram - 2023.11.09 solution

class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        area_of_largest_rectangle = 0
        heights_to_start_indices = []
        i = 0

        for i, h in enumerate(heights):
            area_of_largest_rectangle = max(area_of_largest_rectangle, h)

            while len(heights_to_start_indices) > h:
                heights_to_start_indices.pop()

            for hj, j in enumerate(heights_to_start_indices):
                area = (i - j + 1) * (hj + 1)
                area_of_largest_rectangle = max(area_of_largest_rectangle, area)

            while h > len(heights_to_start_indices):
                heights_to_start_indices.append(i)

            i += 1

        return area_of_largest_rectangle