题目描述
题目描述:
给定一个循环数组(最后一个元素的下一个元素是数组的第一个元素),输出每个元素的下一个更大元素。
数字x的下一个更大的元素是按数组遍历顺序,这个数字之后的第一个比它更大的数,这意味着应该循环地搜索它的下一个更大的数。如果不存在,则输出-1。
示例:
输入: [1,2,1]
输出: [2,-1,2]
解释: 第一个1的下一个更大的数是2;
数字2找不到下一个更大的数;
第二个1的下一个最大的数需要循环搜索,结果也是 2。
注意: 输入数组的长度不会超过 10000。
方法和思路
题目有两个重点
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