84

class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        n = len(heights)
        prev_lt = [i for i in range(n)]
        st_inc_prev = []
        next_lt = [n - i - 1 for i in range(n)]
        st_inc_next = []

        for i, h in enumerate(heights):
            while st_inc_prev and h <= heights[st_inc_prev[-1]]:
                st_inc_prev.pop()
            if st_inc_prev:
                prev_lt[i] = i - st_inc_prev[-1] - 1
            st_inc_prev.append(i)

            while st_inc_next and h < heights[st_inc_next[-1]]:
                x = st_inc_next.pop()
                next_lt[x] = i - x - 1
            st_inc_next.append(i)

        res = 0

        for i in range(len(heights)):
            res = max(res, (1 + prev_lt[i] + next_lt[i]) * heights[i])

        return res