Given a circular integer array nums (i.e., the next element of nums[nums.length - 1] is nums[0]), return the next greater number for every element in nums.
The next greater number of a number x is the first greater number to its traversing-order next in the array, which means you could search circularly to find its next greater number. If it doesn't exist, return -1 for this number.
Example 1:
Input: nums = [1,2,1] Output: [2,-1,2] Explanation: The first 1's next greater number is 2; The number 2 can't find next greater number. The second 1's next greater number needs to search circularly, which is also 2.
Example 2:
Input: nums = [1,2,3,4,3] Output: [2,3,4,-1,4]
Constraints:
1 <= nums.length <= 10^4-10^9 <= nums[i] <= 10^9
The description was taken from https://leetcode.com/problems/next-greater-element-ii/.
#O(N) Time, O(N) Spaceclass Solution:
def nextGreaterElements(self, nums: List[int]) -> List[int]:
output, stack = [-1]*len(nums), []
n = len(nums)
double_nums = nums * 2
for i, num in enumerate(double_nums):
while stack and num > stack[-1][1]:
last_index, last_num = stack.pop()
output[last_index] = num
if i < n:
stack.append((i, num))
return output
Similar to the first variation of this problem, the problem asks us to find the next greater value for each number if it exists.
When we see a requirement like that, a monotonic stack is a good approach.
However, in this variation, we are asked to find a greater element ordered after or before each number within the array, in a circular rotation.
Without using the modulo operator that typically is implemented to handle rotations in lists, we can instead make a new list which we will traverse that will be a doubled copy of the input list.
This way, once we get to the duplicate portion of the input array, we will get to traverse the beginning values of the input array once more and try to find greater values for each number still on the stack.
Let's start by initializing our output and stack, the description wants us to have a negative one signify each value without a greater element so we will initialize each index with a negative one.
output, stack = [-1]*len(nums), []
Next, we will cache the length of the array so that we don't have to keep calculating it within each iteration, and we will create a doubled copy of the input array.
n = len(nums)
double_nums = nums * 2
Now let's begin our enumeration through the doubled array. An enumeration is just a traversal through the values while keeping a counter for us.
for i, num in enumerate(double_nums):
We'll start each iteration by seeing if the current number is greater than what is on the stack.
If that is the case, we will begin popping off any value less than the current number and writing in our output that the greater value for these elements is the current number.
while stack and num > stack[-1][1]:
last_index, last_num = stack.pop()
output[last_index] = num
Once we have popped off each lesser value than the current number from the stack, if the current index is less than the length of the input array, we will append the current index and the current number to the stack.
This will allow us to not add duplicate values to the stack.
if i < n:
stack.append((i, num))
Once we have our output of each greater element for each number, we will return it.
return output