84. Largest Rectangle in Histogram - LeetCode Solution

class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        
        if len(heights) == 0:
            return 0
        
        stack = []

        left = []
        right = []

        stackr = []

        for i in range(len(heights)):

            while len(stack) != 0 and heights[stack[-1]] >= heights[i]:
                stack.pop()

            if len(stack) ==0 :
                left.append(0)
            else:
                left.append(stack[-1]+1)

            stack.append(i)


            while len(stackr) != 0 and heights[stackr[-1]] >= heights[len(heights) - i - 1]:
                stackr.pop()

            if len(stackr) ==0 :
                right.append(len(heights) - 1)
            else:
                right.append(stackr[-1] -1 )

            stackr.append(len(heights) - i - 1 )


        print("Left", left)
        print("right", right[::-1])

        right = right[::-1]

        ans =[]

        for i in range(len(right)):
            ans.append((right[i] - left[i] +1) * heights[i])



        return max(ans)