- 标签：栈、数组、单调栈

- 难度：中等

给定一个循环数组 `nums`（最后一个元素的下一个元素是数组的第一个元素）。

要求：输出每个元素的下一个更大元素。如果不存在，则输出 `-1`。

- 数字 `x` 的下一个更大的元素：按数组遍历顺序，这个数字之后的第一个比它更大的数。这意味着你应该循环地搜索它的下一个更大的数。

第一种思路是根据题意直接暴力求解。遍历 `nums` 中的每一个元素。对于 `nums` 的每一个元素 `nums[i]`，查找 `nums[i]` 右边第一个比 `nums1[i]` 大的元素。这种解法的时间复杂度是 $O(n^2)$。

第二种思路是使用单调递增栈。遍历数组 `nums`，构造单调递增栈，求出 `nums` 中每个元素右侧下一个更大的元素。然后将其存储到答案数组中。这种解法的时间复杂度是 $O(n)$。

而循环数组的求解方法可以将 `nums` 复制一份到末尾，生成长度为 `len(nums) * 2` 的数组，或者通过取模运算将下标映射到 `0` ~ `len(nums) * 2 - 1` 之间。

具体做法如下：

- 使用数组 `res` 存放答案，初始值都赋值为 `-1`。使用变量 `stack` 表示单调递增栈。

- 遍历数组 `nums`，对于当前元素：

- 如果当前元素值小于栈顶元素，则说明当前元素「下一个更大元素」与栈顶元素的「下一个更大元素」相同。应该直接让当前元素的下标入栈。

- 如果当前元素值大于栈顶元素，则说明当前元素是之前元素的「下一个更大元素」，则不断将栈顶元素出栈。直到当前元素值小于栈顶元素值。

- 出栈时，出栈元素的「下一个更大元素」是当前元素。则将当前元素值存入到答案数组 `res` 中出栈元素所对应的位置中。

- 最终输出答案数组 `res`。

size = len(nums)

res = [-1 for _ in range(size)]

stack = []

for i in range(size * 2):

while stack and nums[i % size] > nums[stack[-1]]:

index = stack.pop()

res[index] = nums[i % size]

stack.append(i % size)

return res