Solutions

# Monotonic stack with tuple[idx, height]. Pop if the height decreases. At every pop compute the max_area = h_pop * (i - idx). Consume remaining stack elements at the end.
# stack

# Stack: O(n) time, O(n) space
def largestRectangleArea(heights: list[int]) -> int:
    stack = []
    largest_area = 0

    for i, h in enumerate(heights):

        start = i
        while stack and stack[-1][1] > h:
            idx_pop, h_pop = stack.pop()
            max_area = h_pop * (i - idx_pop)
            largest_area = max(largest_area, max_area)
            start = idx_pop

        stack.append((start, h))

    # Consume remaining items in the stack
    for i, h in stack:
        max_area = h * (len(heights) - i)
        largest_area = max(largest_area, max_area)

    return largest_area


# Brute force: O(n^2), for every bar, find the max area by expanding left and right

if __name__ == '__main__':
    assert largestRectangleArea([2,1,5,6,2,3]) == 10
    assert largestRectangleArea([2,4]) == 4