503. Next Greater Element II

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. If it doesn’t exist, return -1 for this number.

https://leetcode.com/problems/next-greater-element-ii/

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⁴
-10⁹ <= nums[i] <= 10⁹

Test Cases

1 2	class Solution: def nextGreaterElements(self, nums: List[int]) -> List[int]:

solution_test.py

import pytest

from solution import Solution
from solution2 import Solution as Solution2


@pytest.mark.parametrize('nums, expected', [
    ([1,2,1], [2,-1,2]),
    ([1,2,3,4,3], [2,3,4,-1,4]),
])
@pytest.mark.parametrize('sol', [Solution(), Solution2()])
class Test:
    def test_solution(self, sol, nums, expected):
        assert sol.nextGreaterElements(nums) == expected

Thoughts

496. Next Greater Element I 的进阶版，数组变成循环数组，可以跨过数组最右端，从最左端重入数组继续查找 next greater 元素。

假设把 nums 复制一份，拼在原数组的右边，形成 2n 大小的新数组，就能实现循环找 next greater 的效果。实践中不用真的复制，只需要用 1475. Final Prices With a Special Discount in a Shop 中提到的单调栈对 nums 处理两遍，效果是一样的。

需要注意在 problem 496 中，nums2 中的元素各不相同，所以不用特别考虑相等的边界情况。本题 nums 中可能有相等的元素，循环两遍更会产生相等元素，需要处理好相等的边界条件。

Code

Backward Iteration

solution.py

class Solution:
    def nextGreaterElements(self, nums: list[int]) -> list[int]:
        n = len(nums)
        result = [-1] * n

        stack = []
        for _ in range(2):
            for i in range(n - 1, -1, -1):
                val = nums[i]
                while stack and stack[-1] <= val:
                    stack.pop()

                if stack: result[i] = stack[-1]
                stack.append(val) # val is greater than stack[-1].

        return result

Forward Iteration

solution2.py

class Solution:
    def nextGreaterElements(self, nums: list[int]) -> list[int]:
        n = len(nums)
        result = [-1] * n
        stack = []
        for _ in range(2):
            for i, val in enumerate(nums):
                while stack and nums[stack[-1]] < val:
                    result[stack.pop()] = val
                stack.append(i)

        return result