857. The Best Minimum For Every Window Size
Read n values. For every window size k from 1 to n, find the LARGEST value that the minimum
of a window of that size can take:
answer[k] = max over all windows of length k of ( minimum of that window )
Print the n answers in order of increasing k, on one line separated by single spaces.
10 20 30 50 10 70 30 -> 70 30 20 10 10 10 10
1 2 3 4 5 -> 5 4 3 2 1
3 3 3 3 -> 3 3 3 3
For k = 1 the answer is always the largest value in the array; for k = n it is always the
smallest. In between, the answers can only fall, since any window of size k contains a window of
size k - 1 whose minimum is at least as large.
## Why the obvious approach fails twice over
Running a sliding-window minimum for each k separately is O(n) per size and O(n^2) overall.
At n = 200000 that is 4 * 10^10 operations, and it repeats almost all of its work: the same
windows are re-scanned n times.
## Turning the question inside out
Instead of asking "for this size, which window is best", ask "for this value, what is the largest window in which it is the minimum". That largest window is bounded by the nearest STRICTLY SMALLER value on each side:
width[i] = nextStrictlySmaller(i) - previousStrictlySmaller(i) - 1
which is exactly problem 838. Now a[i] is achievable as the minimum of some window of size
width[i], so
answer[width[i]] = max( answer[width[i]], a[i] )
## The step that makes it complete
That fills in some sizes and leaves others empty, because not every width occurs. But a[i] is
also the minimum of every SMALLER window inside its own stretch, so the value carries downward:
for k from n-1 down to 1:
answer[k] = max( answer[k], answer[k+1] )
One backward sweep fills every gap and simultaneously enforces the non-increasing shape the answer must have.
Why is that sweep enough, and not an approximation? Every window of size k has a minimum at some
position i, and that window fits inside i's widest stretch, so k <= width[i]. Hence the true
answer[k] is achieved by some a[i] with width[i] >= k, which is precisely what the backward
maximum collects.
## Two things that go wrong
Values may be negative, so the answer array cannot be initialised to 0. Initialise to the smallest
representable value, or rely on the fact that position n is always filled (the global minimum has
width n) and sweep downward from there.
Both boundaries must be strictly smaller. Making one of them loose shortens the widest stretch of a
repeated minimum, and although the backward sweep hides that on simple inputs, 2 2 2 1 2 2 2 is
the kind of row where it shows.
## Related problems
Problem 838 produces exactly the widths this uses. Problem 194 answers a single fixed k with a
monotonic deque, which is a completely different mechanism for a much smaller question.
## Cost
Time O(n), two stack passes plus two linear sweeps. Space O(n).
Constraints - `1 ≤ n ≤ 200000` - `-10^9 ≤ a[i] ≤ 10^9`
Input
The first line contains one integer n.
The second line contains n integers a[0] ... a[n-1].
Output
Print n integers on one line, separated by single spaces: for each window size from 1 to n in order, the largest achievable window minimum. Print no other words.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.