【一天一道Leetcode】下一个更大元素

题目描述

题目描述：

给定一个循环数组(最后一个元素的下一个元素是数组的第一个元素)，输出每个元素的下一个更大元素。

数字x的下一个更大的元素是按数组遍历顺序，这个数字之后的第一个比它更大的数，这意味着应该循环地搜索它的下一个更大的数。如果不存在，则输出-1。

示例：

输入: [1,2,1]
输出: [2,-1,2]
解释: 第一个1的下一个更大的数是2；
数字2找不到下一个更大的数；
第二个1的下一个最大的数需要循环搜索，结果也是 2。

注意: 输入数组的长度不会超过 10000。

02

方法和思路

题目有两个重点

1.如何求下一个更大的元素

2.如何实现循环数组

如何求下一个更大的元素，可以采用构建单调栈的方法来实现，单调栈是说栈里面的元素从栈底到栈顶是单调递增或者单调递减的。

建立[单调递减栈]，并对原数组进行遍历操作：

如果栈为空，

则把当前元素放入栈内；

如果栈不为空，

则需要判断当前元素和栈顶元素的大小：

如果当前元素比栈顶元素大：

说明当前元素是前面一些元素的[下一个更大元素]，则逐个弹出栈顶元素，直到当前元素比栈顶元素小为止。

如果当前元素比栈顶元素小：

说明当前元素的[下一个更大元素]与栈顶元素相同，则把当前元素入栈。

如何实现循环数组

何为循环数组，即为数组的最后一个元素的下一个元素是数组的第一个元素

即nums=[1, 2, 1]
循环数组为nums[2]=1的下一个元素是nums[0]=1

对于循环数组，我们可以把这个循环数组“拉直”，即复制该数组前n-1个元素拼接在原数组的后面。

即原数组nums=[1, 2, 1]
循环数组xnums=[1, 2, 1, 1, 2]

同时对于新构建的循环数组，

可以使用取模运算%可以把下标i映射到

原数组nums长度的0−N内

综上所述，我们的代码为

class Solution:
    def nextGreaterElements(self, nums: List[int]) -> List[int]:
        N=len(nums)
        ret=[-1]*N
        stack=list()

        for i in range(N*2-1):
            while stack and nums[stack[-1]]<nums[i%N]:
                ret[stack.pop()]=nums[i%N]
            stack.append(i%N)
        return ret