LeetCode 84: Largest Rectangle In Histogram — Step-by-Step Visual Trace

Hard — Stack | Array | Monotonic Stack | Histogram The Problem Find the area of the largest rectangle that can be formed in a histogram represented by an array of bar heights. Each bar has width 1 and the rectangle must be formed by consecutive bars. Approach Use a monotonic stack to track indices of bars in increasing height order. When a shorter bar is encountered, calculate rectangles using previously stored taller bars as heights, with widths determined by the current position and stack contents. Time: O(n) · Space: O(n) Code class Solution : def largestRectangleArea ( self , heights : List [ int ]) -> int : stack = [] max_area = 0 for i in range ( len ( heights )): while stack and heights [ i ] < heights [ stack [ - 1 ]]: height = heights [ stack . pop ()] width = i if not stack else i - stack [ - 1 ] - 1 max_area = max ( max_area , height * width ) stack . append ( i ) while stack : height = heights [ stack . pop ()] width = len ( heights ) if not stack else len ( heights ) - sta