156. Previous Greater Element
Core1000 ms256 MBSolved by 0%
For each element, print the nearest value to its LEFT that is strictly larger
than it, or -1 if there is none.
Print all n answers on one line, separated by single spaces.
Looking left rather than right changes when you can answer, and makes the code simpler, not harder.
Constraints - `1 ≤ n ≤ 200000` - `-1000000000 ≤ a[i] ≤ 1000000000`
Input
The first line contains an integer n.
The second line contains n space-separated integers.
Output
Print n integers on ONE line, separated by single spaces, each element's answer, or -1.
Input5
2 5 3 7 1
Output-1 -1 5 -1 7
Notehas answers at varying distances to the left
Input4
1 2 3 4
Output-1 -1 -1 -1
Noteis ascending, so nothing has a greater element to its left
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.
Hint 1Where to start
Hint 2The approachOpen hint 1 first. This one carries on from it.
Hint 3PseudocodeOpen hint 2 first. This one carries on from it.
Hint 4Full solutionOpen hint 3 first. This one carries on from it.