Why it works
- A number waits on the stack until the first greater number comes; that one pops it, so it is exactly its next greater. The numbers on the stack only fall towards the top, so a greater number pops them from the top down and the loop stops at the first one it does not beat.
- All numbers are distinct, so the number itself can be the key of the map and the stack can hold numbers, not indices.
- A number left on the stack at the end has nothing greater after it. It never gets into the map, so its lookup gives -1.
Complexity
Time O(n + m) for n numbers in nums2 and m in nums1: each number of nums2 is pushed once and popped at most once, and each lookup is O(1). Memory O(n) for the map and the stack.
nextNow solve it yourself, no hints.
Solve on LeetCode ↗