84. Largest Rectangle in Histogram

https://leetcode.com/problems/largest-rectangle-in-histogram/

O(N^2) Solution

TLE

class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        res = 0
        n = len(heights)
        for i in range(n):
            minHeight= float("inf")
            for j in range(i,n):
                minHeight = min(minHeight,heights[j])
                res= max(res,(j-i+1)*minHeight)
        return res

Optimization O(N)

class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        res = 0
        n = len(heights)
        #leftmost idx heights[idx] > heights[i]
        left = [0]*n
        right = [0]*n
        for i in range(n):
            left[i] = i
            while left[i]-1 >= 0 and heights[left[i]-1] >= heights[i]:
                left[i] = left[left[i]-1]
        
        for i in range(n-1,-1,-1):
            right[i] = i
            while right[i] + 1 < n and heights[right[i]+1] >= heights[i]:
                right[i] = right[right[i]+1]
        
        for i in range(n):
            res = max(res,(right[i]-left[i]+1)*heights[i])
        return res

O(N) Mono Increasing Stack