LeetCode 84 Largest Rectangle in Histogram - Implementation

Monotonic increasing stack. Pop when shorter bar found, calculate area.

function largestRectangleArea(heights): heights.append(0) stack = [] maxArea = 0 for i in range(len(heights)): while stack and heights[i] < heights[stack[-1]]: h = heights[stack.pop()] w = i if not stack else i - stack[-1] - 1 maxArea = max(maxArea, h * w) stack.push(i) return maxArea

$O(n)$ time, $O(n)$ space.