Circular Greater Element to the Right
You are given a list of integers nums
. Return a new list of the same length where the value at index i
is set to the next element greater than nums[i]
to its right, circling back to the front of the list if necessary. If there’s no number that’s greater, then it should be set to -1
.
Constraints
n ≤ 100,000
wheren
is the length ofnums
https://binarysearch.com/problems/Circular-Greater-Element-to-the-Right
ExamplesPermalink
Example 1Permalink
Input
- nums =
[3, 4, 0, 2]
Output
- answer =
[4, -1, 2, 3]
SolutionPermalink
class Solution: | |
def solve(self, nums): | |
# use a monotonic stack to store decreasing nums | |
stack = [] | |
res = [-1] * len(nums) | |
for idx, num in enumerate(nums * 2): | |
while stack and nums[stack[-1]] < num: | |
# pop until we can store this num | |
# for each popped, set result to this num | |
# as this is the first num > popped | |
res[stack.pop()] = num | |
if idx < len(nums): | |
stack.append(idx) | |
return res |
Leave a comment