Banner across the silos

A grain co-op wants one rectangular banner strapped flat across its silos. It cannot overhang, so the shortest silo it covers decides how tall it can be.

The problem

The silos stand shoulder to shoulder, each one metre wide, each with its own height. A banner covers a run of consecutive silos, and its height is capped by the shortest of them — anything taller would stand off that one's roofline. So a banner over silos i through j has area (j - i + 1) × min(that run).

The co-op orders one banner, cut as a single rectangle, and wants the biggest the row will take. Report that area.

Input. silos — the silo heights in metres, left to right.

Output. The largest banner area in square metres; an empty row gives 0.

Example.

silos = [3, 9, 7, 8, 4, 6, 6]  ->  24

The winner spans the last six silos at height 4, capped by the 4-metre silo among them: 6 × 4 = 24. Neither the tallest silo (9 alone) nor the whole row (7 silos capped at 3, worth 21) beats it.

A second example, where the tallest silo is not the answer either:

silos = [2, 4, 6, 8]   ->  12
silos = [5, 5, 5, 5]   ->  20

On the rising row the best banner is 6 metres over two silos, tying with 4 metres over three; the 8-metre silo alone is worth 8. The flat row takes everything.

Constraints.

• 0 <= len(silos) <= 10^5
• 1 <= silos[i] <= 10^4

Hints

Approach

Brute force

Try every run: fix a left end, extend right, keep the running minimum. That is n(n + 1)/2 runs — about 5 × 10^9 evaluations at 10^5 silos, recomputing the same minima over and over.

The insight

Every candidate banner is pinned by exactly one silo, the shortest it covers — so stop enumerating runs and instead ask each silo how far it can spread before it meets something shorter.

That turns the search into n questions, each with two halves: the nearest shorter silo left and right. A stack of indices with increasing heights answers both at once. A silo stays on it while everything to its right is at least as tall; when a shorter silo arrives it is popped, so the arriving index is its right edge — and by the increasing order, whatever sits underneath it is its left edge.

Algorithm

1. Keep a stack of silo indices with increasing heights, and a running best of 0.
2. Sweep i left to right, with a virtual silo of height 0 just past the end.
3. While the stack top is at least as tall as the silo at i, pop it: its height is the banner height, i is the first shorter silo to its right, and the new stack top (or -1) is the first shorter silo to its left.
4. The width is i - left - 1; update the best with height × width.
5. Push i. The virtual silo drains whatever is left.

Complexity

Time O(n) — each index is pushed and popped once, each pop constant work. Space O(n) for the stack, which holds the whole row when heights only rise.

Solution

"""Banner across the silos — largest pinned rectangle from a monotonic index stack."""


def solve(silos):
    # Stack invariant: the indices on it have strictly increasing heights, and for
    # each one the index below it is its nearest shorter silo on the left. A silo
    # is popped exactly when its nearest shorter silo on the right arrives, so
    # both edges of its widest banner are known at that single moment.
    rising = []
    best = 0
    end = len(silos)

    for i in range(end + 1):
        height = 0 if i == end else silos[i]   # a zero-height silo past the end drains the stack
        while rising and silos[rising[-1]] >= height:
            pinned = silos[rising.pop()]
            left = rising[-1] if rising else -1
            best = max(best, pinned * (i - left - 1))
        rising.append(i)

    return best

TESTS = [
    (([3, 9, 7, 8, 4, 6, 6],), 24),
    (([2, 4, 6, 8],), 12),
    (([5, 5, 5, 5],), 20),
    # A single silo, and an empty row.
    (([7],), 7),
    (([],), 0),
    # A falling row: nothing survives the sweep to the sentinel.
    (([8, 6, 4, 2],), 12),
    # A deep notch splits the row; neither half can borrow the other's width.
    (([10, 1, 10],), 10),
]

Pitfalls

• Leaving the stack undrained. Without the zero-height silo past the end, the indices still on the stack are never measured: on the rising row [2, 4, 6, 8] nothing is popped at all and the answer comes back 0.
• Measuring the width from the popped index instead of the new stack top. height × (i - j) counts only the span to the right, so the banner over [3, 9, 7, 8, 4, 6, 6] shrinks to 21.
• Writing the width as i - left rather than i - left - 1. That counts the shorter silo on the left as part of the run, and the same row reports 28 for a banner that could not lie flat.

Variants

• The next lot to beat it — the same stack the other way up: it pops on a larger arrival and needs one edge, not two.
• Stacks and monotonic stacks — the lesson on why the popped element is the one whose answer just arrived.