503. Next Greater Element II (Python)

Related Topic

Stack.

Description

Given a circular array (the next element of the last element is the first element of the array), print the Next Greater Number for every element. 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, output -1 for this number.

Sample I/O

Example 1

Input: [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.

Methodology

This is an extention question of 496. Next Greater Element I Instand of using 2 regular arrays, now we use 1 circular array and duplcates allowed.

We need to cancatenate the circular array to its original circular array (in case the next greater element of last digit is before its position), we also need to init the result array with all value equal -1. We double the index size then iterate the index. We use stack to store the greater or equal elements temporarily. Each time, if we find the element that greater than the top element of stack, we pop out the index from stack and change the value of corresponed index in result array. Then we continuely check the new top of the stack until top is greater than current.

def nextGreaterElements(self, nums: List[int]) -> List[int]:
        size = len(nums)
        nums+=nums
        res = [-1] * size
        stack = []
        for i in list(range(size))*2:
            while stack and (nums[stack[-1]] < nums[i]):
                res[stack.pop()] = nums[i]
            stack.append(i)
        return res

BigO

The worst case will happen if the given circular array is in descending order. This will cause O(3n) time complexity. Otherwist the time complexity is approximately O(2n)