Maximum of Minimums for Every Window Size
For every window size 1..n, find the maximum over all windows of that size of the window's minimum.
Open on GeeksforGeeks ↗Intuition
Flip the question per element: for how large a window is a[i] the minimum? Exactly the stretch between its previous-smaller and next-smaller neighbours. Each element then bids for that window size; propagate bids down to smaller sizes.
Invert the question. Instead of asking each window for its minimum, ask each element for the largest window in which it is the minimum — that span runs between its previous-smaller and next-smaller elements, both from monotonic stacks. A final suffix-max pass fills sizes no element claimed directly.
Approach
Previous & next smaller via stacks
Two monotonic-stack passes give, for each i, the nearest smaller element on each side — the window where a[i] rules as minimum has length len = next[i] − prev[i] − 1.
Bid on the answer array
ans[len] = max(ans[len], a[i]): the best minimum achievable for that exact window length.
Fill gaps right-to-left
A great minimum for length L also works for any shorter window inside it, so ans[k] = max(ans[k], ans[k+1]) sweeping down.
Solution & live demo
Common pitfalls
Computing every window explicitly
for k in range(1, n + 1):
ans[k] = max(min(a[i:i+k]) for i in range(n - k + 1))length = nxt[i] - prev[i] - 1 ans[length] = max(ans[length], a[i])
That's O(n³). Each element is the minimum of exactly one maximal span, so computing that span with two stack passes answers every window size in O(n).
Skipping the suffix-maximum pass
return ans[1:]
for k in range(n - 1, 0, -1):
ans[k] = max(ans[k], ans[k + 1])
return ans[1:]Some window sizes are never any element's maximal span and are left at 0. But an element that is the minimum of a length-5 window is also the minimum of some length-4 window inside it, so answers propagate downward from larger sizes.
Using the same strictness in both stack passes
while stack and a[stack[-1]] >= a[i]: pop # in both loops
# previous smaller: >= # next smaller: >
With equal values, using the same comparison on both sides makes two identical elements claim overlapping spans and one of them is measured too short. Making one side strict and the other non-strict assigns each span to exactly one representative.
Edge cases
Each element's window runs to the right edge; the sweep fills every size correctly.
Use strict inequality on one side only to avoid double-counting equal spans.