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
time, space.