📢📢📢📣📣📣
🐸Hello，大家好我是Dream，欢迎大家来到刷题乐园😜😜😜
🐹游园须知： 本乐园从不缺乏天才，努力才是你的最终入场券！🚀🚀🚀
🐹导游主要使用Python语言，同时欢迎其他语言的小伙伴进来玩耍☀️☀️☀️
🐹游园过程中，如果发现有错误的话，欢迎大家评论区及时斧正❤️❤️❤️
🐹最后，祝大家游园愉快，一起加油进步🍺🍺🍺

💦乐园描述

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

示例 1:

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

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
 

💦游园准备

🚀今天游玩的两个重点：

• 如何求下一个更大的元素
• 如何实现循环数组

🏳️‍🌈错误游玩：本题如果暴力求解，对于每个元素都向后去寻找比它更大的元素，那么时间复杂度 O(N^2) 会超时。必须想办法优化。

🏳️‍🌈正确游玩：根据上面的分析可知，可以遍历一次数组，如果元素是单调递减的（则他们的「下一个更大元素」相同），我们就把这些元素保存，直到找到一个较大的元素；把该较大元素逐一跟保存了的元素比较，如果该元素更大，那么它就是前面元素的「下一个更大元素」。

❄️在实现上，我们可以使用「单调栈」来实现，单调栈是说栈里面的元素从栈底到栈顶是单调递增或者单调递减的（类似于汉诺塔）

❄️栈的相关操作如下：

• Stack() 创建一个空的新栈。 它不需要参数，并返回一个空栈。
• push(item)将一个新项添加到栈的顶部。它需要 item 做参数并不返回任何内容。
• pop() 从栈中删除顶部项。它不需要参数并返回 item 。栈被修改。
• peek() 从栈返回顶部项，但不会删除它。不需要参数。 不修改栈。
• isEmpty() 测试栈是否为空。不需要参数，并返回布尔值。
• size() 返回栈中的 item 数量。不需要参数，并返回一个整数。

💦开始游玩

✍我们使用单调栈时，保存的是元素对应的下标。而这个单调栈是 单调不升，即是栈底到栈顶中存储下标对应的元素值是单调递减的。下面是具体的思路：
✍声明单调栈 stack，开始遍历数组；
✍当栈非空时，直接将遍历元素对应的下标压入栈中；
✍当栈为空时，需要比较栈顶下标对应元素值与当前元素值的大小：

• 若栈顶下标对应元素值 当前元素值时，弹出栈顶下标，根据下标在结果列表中找到对应的元素，其下一个更大的元素则为当前元素。（这里需要循环比较判断，直到栈顶下标对应的元素值大于当前元素停止）
• 若栈顶下标对应元素值 ≥ 当前元素值时，只需要将当前元素对应的下标压入栈中，不做其他处理。

class Solution:
    def nextGreaterElements(self, nums: List[int]) -> List[int]:
        n = len(nums)
        
        res = [-1] * n
        stack = []
        # 遍历
        for i in range(2 * n - 1):
            # 栈非空，出栈比较栈顶索引对应元素值与当前元素值的大小
            while stack and nums[stack[-1]] < nums[i % n]:
                res[stack.pop()]  = nums[i % n]
            # 压入栈中的是元素的索引
            # 这里用取模的方法映射索引到原数组中
            stack.append(i % n)
        
        return res

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
 

💦游玩总结

The stage extends as far as the heart goes~加油！❤️❤️❤️

**🏅今天是我打卡的第一天，希望每天都能见到最棒的你🏅**

好啦，这就是今天要给大家分享的全部内容了
❤️❤️❤️如果你喜欢的话，就不要吝惜你的一键三连了~

文章来源: xuyipeng.blog.csdn.net，作者：是Dream呀，版权归原作者所有，如需转载，请联系作者。

原文链接：xuyipeng.blog.csdn.net/article/details/119709925