Learning On the Way

84. Largest Rectangle in Histogram

Given n non-negative integers representing the histogram's bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.

class Solution: 
    def largestRectangleArea(self, heights: List[int]) -> int: 
        stack = [-1] # Record the last index that is smaller 
        heights += [-1] # Add it to clear out the stack at the end 
        area = 0 
         
        for i, height in enumerate(heights):  
            # When it is equal, still need to update because you want the "last" index that is smaller than the current 
            while (stack[-1] != -1 and heights[stack[-1]] >= height): 
                idx = stack.pop() 
                area = max(area, (i - stack[-1] - 1) * heights[idx]) 
             
            stack.append(i) 
        return area