Next Greater Element II — LeetCode 503 Python Solution

The problem

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.

Example

Input

nums = [1,2,1]

Output

[2,-1,2]

Explanation

The first 1's next greater number is 2;

Python solution

class Solution:
    def nextGreaterElements(self, nums: List[int]) -> List[int]:
        n = len(nums)
        ans = [-1] * n
        stk = []
        for i in range(n * 2 - 1, -1, -1):
            i %= n
            while stk and stk[-1] <= nums[i]:
                stk.pop()
            if stk:
                ans[i] = stk[-1]
            stk.append(nums[i])
        return ans

Complexity

Pattern: Stack

When the most recent unresolved thing is the one that matters, use a stack. LeetCode 503. Next Greater Element II is filed here because LeetCode tags it Stack, which is the vocabulary this hub collects.

The stack guide has the Python template for the pattern and the 194 LeetCode problems that use it.

Related problems