开发者社区> 游客z3jcatjk57fiu> 正文
阿里云
为了无法计算的价值
打开APP
阿里云APP内打开

每日算法系列【LeetCode 503】下一个更大元素 II

简介: 给定一个循环数组(最后一个元素的下一个元素是数组的第一个元素),输出每个元素的下一个更大元素。数字 x 的下一个更大的元素是按数组遍历顺序,这个数字之后的第一个比它更大的数,这意味着你应该循环地搜索它的下一个更大的数。如果不存在,则输出 -1。
+关注继续查看

题目描述


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

示例1

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

提示输入数组的长度不会超过 10000。

题解


这题中循环数组其实不用管,只需要再复制一遍数组接在后面就行了,那么关键还是如何求每个数后面第一个比它大的数。

我们可以从右往左遍历数组,如果遍历到某个数,那么它右边所有比它小的数都不用再考虑了。因为再继续遍历下去的话,它右边比它还小的数是绝对不可能成为第一个大的数的。

image.png

代码


c++

class Solution {
    public:  
    vector<int> nextGreaterElements(vector<int>& nums) { 
        int n = nums.size(); 
        stack<int> st;     
        vector<int> res(n, -1);  
        for (int i = 2*n-2; i >= 0; --i) {  
            while (!st.empty() && nums[i%n] >= st.top()) {   
                st.pop();    
            }         
            res[i%n] = st.empty() ? -1 : st.top();  
            st.push(nums[i%n]);   
        }     
        return res;  
    }
};

python

class Solution:
    def nextGreaterElements(self, nums: List[int]) -> List[int]: 
        n = len(nums)   
        stack, res = [], [-1] * n   
        for i in range(2*n-2, -1, -1):  
            while len(stack) > 0 and nums[i%n] >= stack[-1]: 
                stack.pop()    
                res[i%n] = -1 if len(stack)==0 else stack[-1] 
                stack.append(nums[i%n])   
                return res

image.png

作者简介:godweiyang知乎同名华东师范大学计算机系硕士在读,方向自然语言处理与深度学习喜欢与人分享技术与知识,期待与你的进一步交流~


版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
每日算法系列【LeetCode 376】摆动序列
如果连续数字之间的差严格地在正数和负数之间交替,则数字序列称为摆动序列。第一个差(如果存在的话)可能是正数或负数。少于两个元素的序列也是摆动序列。
24 0
每日算法系列【LeetCode 810】黑板异或游戏
一个黑板上写着一个非负整数数组 nums[i] 。小红和小明轮流从黑板上擦掉一个数字,小红先手。如果擦除一个数字后,剩余的所有数字按位异或运算得出的结果等于 0 的话,当前玩家游戏失败。 (另外,如果只剩一个数字,按位异或运算得到它本身;如果无数字剩余,按位异或运算结果为 0。) 换种说法就是,轮到某个玩家时,如果当前黑板上所有数字按位异或运算结果等于 0,这个玩家获胜。 假设两个玩家每步都使用最优解,当且仅当小红获胜时返回 true。 示例1
27 0
每日算法系列【LeetCode 927】三等分
给定一个由 0 和 1 组成的数组 A,将数组分成 3 个非空的部分,使得所有这些部分表示相同的二进制值。
32 0
LeetCode(算法)- 101. 对称二叉树
LeetCode(算法)- 101. 对称二叉树
12 0
LeetCode 5. 最长回文子串 | 算法-从菜鸟开始
本文是《算法-从菜鸟开始》系列文章的第6篇,欢迎收藏、留言、点赞。 话不多说,让我们继续我们的算法之旅。
14 0
leetcode算法83.删除排序链表中的重复元素
本文讲解如何用leetcode算法83.删除排序链表中的重复元素。
21 0
leetcode算法219.存在重复元素 II
给你一个整数数组 nums 和一个整数 k ,如何判断数组中是否存在两个不同的索引 i 和 j ,满足 nums[i] == nums[j] 且 abs(i - j) <= k ?本文带大家解决这个问题。
22 0
leetcode算法101.对称二叉树
当给你一个二叉树的根节点 root 时,如何 检查它是否轴对称?本文带大家解决这个问题。
22 0
217
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
低代码开发师(初级)实战教程
立即下载
阿里巴巴DevOps 最佳实践手册
立即下载
冬季实战营第三期:MySQL数据库进阶实战
立即下载