438. Circular Next Bigger
A carousel has seats arranged in a ring, and each seat shows the score of the child sitting there. A child looks around, starting at the next seat clockwise and continuing around the ring, searching for the first score that is strictly larger than their own.
Given the array nums listing the scores in clockwise order, where the last seat is followed by the first one, return an array ans of the same length. ans[i] is the first larger score met when walking from seat i around the ring at most once, or -1 if no seat holds a larger score. The ring can have up to 100,000 seats.
Example 1
- Input:
- nums = [24,37,9,37,15,28]
- Output:
- [37,-1,37,-1,28,37]
- Explanation:
From 24 the next larger is 37. From the first 37 nothing larger exists. From 9 it is the second 37. From 15 it is 28. From 28 walking around the ring the first larger score is 37 (the first seat).
Example 2
- Input:
- nums = [6,2,6,1]
- Output:
- [-1,6,-1,6]
- Explanation:
The first 6 and the other 6 see nothing larger anywhere in the ring. The 2 meets the second 6, and the 1 wraps around to the first 6.
Constraints
1 ≤ nums.length ≤ 105
-109 ≤ nums[i] ≤ 109
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 200 msC++ 50 msJava 100 msJavaScript 100 msTypeScript 100 ms
Expected complexity
- Time
- O(n)
- Space
- O(n)