leetcode代码记录（下一个更大元素 II

1. 题目：

给定一个循环数组 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]

2. 我的代码：

class Solution:
    def nextGreaterElements(self, nums: List[int]) -> List[int]:
        # 环形结构 可以重复两次
        nums_new = nums[:] + nums[:]
        # 单调栈
        stack = []
        
        result = [-1] * len(nums_new)

        # 循环
        stack.append(0)
        for i in range(1, len(nums_new)):
            while stack != [] and nums_new[i] > nums_new[stack[-1]]:
                k = stack.pop()
                result[k] = nums_new[i]

            stack.append(i)

        # 根据映射得到最终结果
        return result[:len(nums)]

这道题很明显也是利用单调栈求得下一个更大元素，但问题是，这是个环形的数组。后面的元素有在普通数组里找不到下一个最大元素，而在循环到第二圈的时候能找到最大元素的风险。因此，这里可以重复两次，因为一定不会超过两次，计算两倍nums长度的新nums的结果。最后把结果截前一半即可（因为后一半可能任然存在问题，我们重复两次就是为了前一半能够全部正确）。