836. The Nearest Bigger Value on Either Side
Read n values. For each position, find the CLOSEST position holding a strictly larger value,
looking in BOTH directions, and print the distance to it. If no position anywhere in the array
holds a strictly larger value, print -1 for that position.
Print the n answers on one line, separated by single spaces.
2 5 3 1 4 2 -> 1 -1 1 1 3 1
5 5 5 5 5 -> -1 -1 -1 -1 -1
1 2 3 4 -> 1 1 1 -1
Position 5 in the first row holds 4. Nothing to its right beats it, and to the left the nearest larger value is the 5 three places back, so the answer is 3. The maximum of the whole array never has an answer.
## Why the search does not have to be a search
The wasteful reading of this problem is a widening ring: check one step out, then two, then three.
On 1 1 1 ... 1 1000000000 1 1 ... 1 the positions far from the middle walk half the array each,
so it is O(n^2).
The key observation removes the ring entirely. Looking LEFT, the nearest strictly larger value is the PREVIOUS greater element, because anything further left that is larger is by definition further away. Looking RIGHT, it is the NEXT greater element. So the answer is
min( i - previousGreater(i) , nextGreater(i) - i )
with a missing side treated as infinitely far, and -1 when both are missing. There is no search,
only two scans.
## The two scans, and why both stacks decrease
Left to right, keep a stack of positions. Before handling i, pop every position whose value is
LESS THAN OR EQUAL TO a[i], since none of them can ever be the previous strictly greater
element of anything from here on. Whatever is left on top is previousGreater(i). Then push i.
Right to left, do exactly the same thing in mirror image to get nextGreater(i).
Both stacks are kept DECREASING because the question asks for something BIGGER. The pop test is
<= rather than < because an equal value is not strictly larger and therefore is not an
acceptable answer, so it must not be allowed to sit on the stack blocking the real one.
## The case that catches people
7 7 8 7 7 6 8 5 9 at position 3 (the 8): its previous greater does not exist, and its next
greater is the 9 six places away, so the answer is 6, not 1. Anyone who pops on < keeps equal
values on the stack and reports a neighbour that is merely equal.
## Related problems
Problem 156 asks for the previous greater VALUE and stops there. This one needs both sides and converts to distance, which is what a two-sided width measurement always looks like; problem 838 does the same for the other comparison.
## Sizes and widths
Values reach 10^9 and every answer is a distance, at most n, or -1. Nothing is accumulated,
so 32 bits holds the whole computation.
## Cost
Time O(n), two passes, each with n pushes and at most n pops. 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 position, the distance to the nearest strictly larger value in either direction, or -1 if there is none. Print no other words.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.