DiffPush Tier Stack and Queues · Monotonic Stack and Queue O(n) · O(n)
A port stacks shipping containers in vertical columns of varying heights, all one unit wide. Customs needs the largest rectangle of contiguous clearance the skyline contains — the maximal box that fits under a run of columns without cutting through any container. Each column's best rectangle stretches between its nearest shorter neighbors on both sides.
Input: An integer array heights where heights[i] is the column height at position i.
Output: Return the area of the largest rectangle fitting entirely under the histogram.
1 <= heights.length <= 10^50 <= heights[i] <= 10^4Input: {"heights":[2,1,5,6,2,3]}
Output: 10
Columns 5 and 6 together form a 2-wide, 5-tall rectangle of area 10.
Input: {"heights":[2,4]}
Output: 4
The full-width bar of height 2 gives 4, matching the single column of height 4.