Hints — p54 Largest Rectangle in Histogram

Hint 1. Brute force “try all (l, r) and find the min” is O(n³). “For each i, expand left and right while heights ≥ heights[i]” is O(n²) worst case. You need O(n).

Hint 2. Reframe: every rectangle has a limiting bar (the shortest within its span). Partition all rectangles by “which bar limits me.” Then for each bar i, find the maximal-width rectangle where it’s the limiting (shortest) bar.

Hint 3. That max width = (right_smaller[i] - left_smaller[i] - 1), where left_smaller[i] and right_smaller[i] are the indices of the nearest strictly-shorter bars on each side (or -1 / n if none).

Hint 4. Compute left_smaller and right_smaller each in one monotonic-stack pass. Or fuse into one pass: maintain a monotonic INCREASING stack of indices; when a smaller bar h arrives, pop and resolve — at that moment you know both boundaries.

Hint 5. One-pass trick: append a sentinel 0 to the end of heights. That forces every remaining bar to be popped (since 0 is smaller than anything), avoiding a separate drain loop. For each popped top: width = i - (stack[-1] if stack else -1) - 1, area = heights[top] * width.

If still stuck: see solution.py.