难度: Medium
给定一个循环数组 nums （ nums[nums.length - 1] 的下一个元素是 nums[0] ），返回 nums 中每个元素的 下一个更大元素 。
数字 x 的 下一个更大的元素 是按数组遍历顺序，这个数字之后的第一个比它更大的数，这意味着你应该循环地搜索它的下一个更大的数。如果不存在，则输出 -1 。
示例 1:
输入: nums = [1,2,1] 输出: [2,-1,2] 解释: 第一个 1 的下一个更大的数是 2； 数字 2 找不到下一个更大的数； 第二个 1 的下一个最大的数需要循环搜索，结果也是 2。
示例 2:
输入: nums = [1,2,3,4,3] 输出: [2,3,4,-1,4]
提示:
1 <= nums.length <= 104-109 <= nums[i] <= 109运行时间: 256 ms
内存: 16.5 MB
class Solution:
def nextGreaterElements(self, nums: List[int]) -> List[int]:
stack = []
n = len(nums)
nums *= 2
ans = [-1] * len(nums)
for i in range(len(nums)):
while stack and nums[stack[-1]] < nums[i]:
idx = stack.pop()
ans[idx] = nums[i]
stack.append(i)
return ans[:n]
这个题解使用单调栈的思路来解决问题。首先将原数组复制一遍拼接到原数组后面，模拟循环数组。然后遍历拼接后的数组，对于每个元素，将栈中所有小于当前元素的元素弹出，并将当前元素作为它们的下一个更大元素。最后将当前元素的索引压入栈中。遍历结束后，取ans数组的前n个元素作为最终结果返回。
时间复杂度: O(n)
空间复杂度: O(n)
class Solution:
def nextGreaterElements(self, nums: List[int]) -> List[int]:
stack = []
n = len(nums)
nums *= 2 # 复制数组，模拟循环数组
ans = [-1] * len(nums) # 初始化结果数组，默认值为-1
for i in range(len(nums)):
# 将栈中所有小于当前元素的元素弹出，并更新它们的下一个更大元素
while stack and nums[stack[-1]] < nums[i]:
idx = stack.pop()
ans[idx] = nums[i]
stack.append(i) # 将当前元素的索引压入栈中
return ans[:n] # 返回ans数组的前n个元素作为最终结果
单调栈是一种特殊的栈，它在操作过程中会保持元素的单调性（递增或递减）。在这个题解中，使用的是一个单调递减栈，这意味着栈顶到栈底的元素是递减的。这种数据结构对于解决“下一个更大元素”类问题特别有效，因为它可以追踪已遍历元素中未找到更大元素的索引，并快速确定新元素的加入是否可以成为之前某些元素的“下一个更大元素”。当遇到一个新元素时，如果它比栈顶元素大，则栈顶元素的下一个更大元素就是这个新元素，接着将栈顶元素弹出，并继续此过程直到栈顶元素大于或等于当前元素或栈为空，然后将当前元素的索引压入栈，以供后续使用。
在循环数组中，数组的末尾元素后面是数组的开头元素，这种循环关系在普通的线性数组中不易处理特别是在索引管理上。通过将原数组复制并拼接到其后面，我们可以通过线性遍历（即遍历这个扩展的数组）的方式简化问题的复杂性，使得每个元素都可以直接找到其后面的元素而无需考虑边界。此外，这种方法也方便使用单调栈处理，因为我们可以一次性地处理所有的关系而无需在数组末尾再进行额外的循环判断和索引调整。
因为题解中将原数组复制并拼接到了自己的后面，所以新的数组长度变为了2n。在遍历这个长度为2n的数组时，我们需要记录每个位置的下一个更大元素，即使是复制的部分。虽然最终只需要原始数组长度n的结果，初始化长度为2n是为了在处理过程中能够存储所有可能的结果，确保不会因为索引超出范围而导致错误。遍历结束后，我们只取结果数组的前n个元素作为最终答案。
如果数组是降序排列的，每个元素都比前一个元素小，那么在使用单调递减栈的情况下，这些元素会依次被压入栈中，因为没有任何一个元素能弹出栈中的元素（没有找到更大的元素）。这将导致栈中元素逐渐增加，直到处理完所有元素。在整个过程中，栈将保存所有元素的索引，因为栈中的每个元素都没有找到比它大的下一个元素，所以结果数组中对应位置都将保持初始化的默认值（如-1）。