437. Next Bigger Lookup
A museum lists the heights of its statues along a hallway, no two statues having the same height. A guide only cares about a handful of statues, and for each of them wants the height of the first statue standing further down the hallway that is taller.
You are given the array nums of all statue heights in hallway order, all distinct, and the array subset of heights the guide cares about, each of which appears in nums. Return an array with one entry per element of subset, in the same order: the height of the first taller statue to the right of that statue in nums, or -1 if there is none. Both arrays can be long, so avoid scanning to the right for every query.
Example 1
- Input:
- subset = [40,15], nums = [22,40,15,31,9,50]
- Output:
- [50,31]
- Explanation:
Right of 40 the taller ones are 50 only, and 15 is followed by 31 first. So the answers are 50 and 31.
Example 2
- Input:
- subset = [9,22,31], nums = [22,9,31,17]
- Output:
- [31,31,-1]
- Explanation:
After 9 the first taller is 31, after 22 it is 31, and nothing taller follows 31, giving -1.
Constraints
0 ≤ subset.length ≤ nums.length ≤ 105
-109 ≤ nums[i] ≤ 109
All values in nums are distinct; every value of subset occurs in nums.
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
Expected complexity
- Time
- O(n + m)
- Space
- O(n)