前往此题

单调栈

这题也是一道典型的单调栈题目，唯一需要注意的是题中的数组是一个循环数组，所以我们在遍历过程中不能将元素入栈，需要将索引值入栈，这样方便实现循环数组。

本题可以分为两个知识点：

• 如何求下一个更大元素
• 如何实现循环数组

做过下一个更大元素这题的应该都知道可以直接用单调栈来得到下一个更大元素。本题的重点在于如何实现一个循环数组。

算法过程

建立单调栈，并遍历数组

1. 如果栈为空，则把当前元素放入栈内
2. 如果栈不为空，则判断栈顶元素与当前元素的大小
   1. 如果当前元素比栈顶元素大：说明当前元素是前面一些元素的“下一个更大元素”，将栈内元素逐个推出，直到当前元素小于栈顶元素
   2. 如果当前元素比栈顶元素小：当前元素入栈

实现循环数组

可以使用取模运算，将索引i映射到长度为N的数组nums，这样不管循环几遍，i % N的取值范围永远是0到N之间。

代码

class Solution:
    def nextGreaterElements(self, nums: List[int]) -> List[int]:
        N = len(nums)
        stack = []
        res = [-1] * N

        for i in range(N*2):
            while stack and nums[stack[-1]] < nums[i % N]:
                res[stack.pop()] = nums[i % N]
            stack.append(i % N)
        return res