Given a circular integer array nums (the element after the last one is the first one), return the next greater number for every element. The next greater number of x is the first strictly larger value you meet when walking forward from x, wrapping around the end if needed. If no such value exists, use -1.
- 1 <= nums.length <= 10^4
- -10^9 <= nums[i] <= 10^9
Give it a real try first. Even 15 minutes of struggle makes the solution stick far better.
Intuition
The brute force walks forward up to n - 1 steps (with wrap) from each element: O(n^2). Wrapping around is the same as searching in the array concatenated with itself, and the monotonic stack already solves next greater for a straight array in O(n). So we iterate twice over the indices with i % n. In the second lap, elements only act as "greater values" for indices still waiting on the stack; anything still waiting after two laps is the maximum and gets -1.
Algorithm
- Fill
answith -1 and create an empty stack of indices. - Loop
ifrom 0 to2n - 1, withv = nums[i % n]. - While the stack is not empty and
nums[top] < v, poptopand setans[top] = v. - If
i < n, pushi. - Return
ans.
O(n)Space: O(n)< when popping: equal values are not "greater". With [3,3,3] every answer must be -1. Do not push indices in the second lap, or the stack grows to 2n and you may write answers twice.class Solution: def nextGreaterElements(self, nums: List[int]) -> List[int]: n = len(nums) ans = [-1] * n stack = [] # indices still waiting for i in range(2 * n): v = nums[i % n] while stack and nums[stack[-1]] < v: ans[stack.pop()] = v if i < n: stack.append(i) # push only in the first lap return ans