寻找数组元素右边第一个比它大的数 - 算法解析及 Python 代码 - 常规

寻找数组元素右边第一个比它大的数 - 算法解析及 Python 代码

题目描述：

给定一个数组，对于每个元素，找到它右边第一个比它大的数，如果不存在，则输出-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 res