class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        n = len(heights)
        if (n == 1):
            return heights[0]
        if (n == 0):
            return 0
        if (n == 2):
            max_high = max(heights)
            min_high = min(heights)
            return max(min_high * 2, max_high)
        min_left = [0 for i in range(n)]
        min_right = [0 for i in range(n)]
        stack = [0]
        for i in range(n):
            while (len(stack) > 0 and heights[i] <= heights[stack[-1]]):
                stack.pop()
            if (len(stack) > 0):
                min_left[i] = stack[-1]
                stack.append(i)
            else:
                stack.append(i)
                min_left[i] = stack[-1]
        stack = [n - 1]
        for i in range(n - 1, -1, -1):
            while (len(stack) > 0 and heights[i] <= heights[stack[-1]]):
                stack.pop()
            if (len(stack) > 0):
                min_right[i] = stack[-1]
                stack.append(i)
            else:
                stack.append(i)
                min_right[i] = stack[-1]
        print(min_left)
        print(min_right)
        min_left[0] = -1
        min_right[n - 1] = n
        max_num = n * min(heights)
        for i in range(n):
            if ((min_right[i] - min_left[i] - 1) * heights[i] > max_num):
                max_num = (min_right[i] - min_left[i] - 1) * heights[i]
        return max_num