leetcode - 503. Next Greater Element II

Description

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

Solution

Monotonous stack, start from right to left.

Think about if it’s not the circular array, then we would start from the right to left, using a monotonous stack. So the elements in the stack would be the elements at the right. Because we want to find greater elements, so the monotonous stack would be a decreasing monotonous stack. So if the top element is greater than the current element, we find our result. Otherwise we need to keep popping the stack until we find one.

Now we have a circular array, the only change is, we don’t start at the right. Instead, we start at the maximum element, and from the maximum element we iterate from right to left. The rest would be the same as above.

Time complexity: $o(n)$
Space complexity: $o(n)$

Code

class Solution:
    def nextGreaterElements(self, nums: List[int]) -> List[int]:
        # find the maximum index
        max_index, max_num = 0, nums[0]
        for i in range(1, len(nums)):
            if max_num < nums[i]:
                max_num = nums[i]
                max_index = i
        # start from the maximum index to the left
        res = [-1] * len(nums)
        res[max_index] = -1
        mono_stack = [max_num]
        index = (max_index - 1) % len(res)
        while index != max_index:
            while mono_stack and mono_stack[-1] <= nums[index]:
                mono_stack.pop()
            res[index] = mono_stack[-1] if mono_stack else -1
            mono_stack.append(nums[index])
            index -= 1
            index %= len(res)
        return res