数组元素右边第一个比它大的数

题目描述：

给定一个数组，对于每个元素，找到它右边第一个比它大的数，如果不存在，则输出-1。

示例：

输入: [4, 5, 2, 25]

输出: [5, 25, 25, -1]

解释:

4 右边第一个比它大的数是 5；

5 右边第一个比它大的数是 25；

2 右边第一个比它大的数是 25；

25 右边没有比它大的数，输出-1。

算法思路：

从右到左遍历数组，用一个栈来保存从右到左遍历过的元素。对于每个元素，如果栈为空，则将-1入栈；否则，如果栈顶元素大于当前元素，则将栈顶元素入栈；否则，弹出栈顶元素，直到栈为空或栈顶元素大于当前元素，然后将当前元素入栈。最后将栈中剩余的元素全部弹出并赋值为-1。

时间复杂度：O(n)

空间复杂度：O(n)

Python代码：

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