leetcode-496-Next Greater Element I

题目描述:

You are given two arrays (without duplicates) nums1 and nums2 where nums1’s elements are subset of nums2. Find all the next greater numbers for nums1's elements in the corresponding places of nums2.

The Next Greater Number of a number x in nums1 is the first greater number to its right in nums2. If it does not exist, output -1 for this number.

Example 1:

Input: nums1 = [4,1,2], nums2 = [1,3,4,2].
Output: [-1,3,-1]
Explanation:
    For number 4 in the first array, you cannot find the next greater number for it in the second array, so output -1.
    For number 1 in the first array, the next greater number for it in the second array is 3.
    For number 2 in the first array, there is no next greater number for it in the second array, so output -1.

Example 2:

Input: nums1 = [2,4], nums2 = [1,2,3,4].
Output: [3,-1]
Explanation:
    For number 2 in the first array, the next greater number for it in the second array is 3.
    For number 4 in the first array, there is no next greater number for it in the second array, so output -1.

Note:

  1. All elements in nums1 and nums2 are unique.
  2. The length of both nums1 and nums2 would not exceed 1000.

要完成的函数:

vector<int> nextGreaterElement(vector<int>& findNums, vector<int>& nums) 

说明:

1、给定两个vector,比如[3,2]和[2,4,3,1],第一个vector是第二个的子集。要求输出第二个vector中比第一个vector中某个元素大,并且位置上也在其右边的数。要是没找到的话,输出-1。

比如我们给出的例子中,3的next greater element没有,所以我们输出-1。2的next greater element是4,所以输出4。

2、理解题意之后,一般想法是双重循环。

我们可以设定第一个vector为vector1,第二个为vector2。

对于每个vector1中的元素,遍历vector2,找到其位置,在其位置右边继续找,直到找到比它大的数值。

双重循环,这道题可解。

代码如下:

    vector<int> nextGreaterElement(vector<int>& findNums, vector<int>& nums) 
    {
        vector<int>::iterator iter;
        vector<int>res;
        for(int i=0;i<findNums.size();i++)
        {
            iter=find(nums.begin(),nums.end(),findNums[i]);//找到位置
            iter++; 
            while(iter!=nums.end())//循环处理,直到找到比它大的数
            { 
                if(*iter>findNums[i])
                {
                    res.push_back(*iter);
                    break;
                }
                else
                    iter++; 
            }
            if(iter==nums.end())//边界情况处理
                res.push_back(-1);
        }    
        return res; 
    } 

上述代码实测13ms,beats 45.84% of cpp submissions。

3、改进:

双重循环实在太浪费信息了。比如[8,7,1,2,3,4,5,6,9,10],我们要找8的next greater element,要比较中间的1/2/3/4/5/6,才能到9;要找7的next greater element,也要比较中间的1/2/3/4/5/6。我们之前比较过一次,但这些信息完全没有被利用到,又重复比较了一次。

我们可以从左边找起,把那些找到了对应值(也就是next greater element)的删去,然后停留在原本vector2中的,可以想到,是一个下降的vector。

在评论区中参考了大神的代码,自己修改了一下,增加了注释,分享给大家。

代码如下:

    vector<int> nextGreaterElement(vector<int>& findNums, vector<int>& nums) 
    {
        stack<int> s1;//存储还没有找到对应值的数
        unordered_map<int, int> m1;//建立对应表
        for (int i=0;i<nums.size();i++) //对每个新的数进行处理
        {
            while (s1.size() && s1.top() < nums[i]) 
            {
                m1[s1.top()] = nums[i];
                s1.pop();
            }
            s1.push(nums[i]);
        }
        vector<int> res;
        for (int i=0;i<findNums.size();i++) 
            res.push_back(m1.count(findNums[i]) ? m1[findNums[i]] : -1);
        return res;
    }

这份代码其实建立了所有能找到next greater element的元素的对应表。

我们当然也可以不用栈来存储,理解起来会更加直接。只不过使用栈使得代码更好写。

上述代码实测11ms,beats 84.93% of cpp submissions。

的确是很优秀的做法。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏java学习

Java每日一练(2017/7/21)

聊天系统 ●我希望大家积极参与答题!有什么不懂可以加小编微信进行讨论 ★珍惜每一天,拼搏每一天,专心每一天,成功每一 如果你是初学者,或者是自学者!你可以加小编...

3344
来自专栏angularejs学习篇

angularjs学习第三天笔记(过滤器第二篇---filter过滤器及其自定义过滤器)

您好,我是一名后端开发工程师,由于工作需要,现在系统的从0开始学习前端js框架之angular,每天把学习的一些心得分享出来,如果有什么说的不对的地方,请多多指...

923
来自专栏编程

Python精华之函数

各位小伙伴,大家周一快乐! 不知道刚刚过去的周末大家过的怎么样? 反正常老师是被糊里糊涂的过了个圣诞节 满大街的商场和超市都张灯结彩,话说,不是有规定不让过这种...

2025
来自专栏Laoqi's Linux运维专列

Python for 循环语句

4688
来自专栏吴裕超

es6 Object的几个新方法

ES5 的 Object.preventExtensions 则可以阻止给对象添加新属性

1013
来自专栏北京马哥教育

Python编程中的反模式

云豆贴心提醒,本文阅读时间7分钟 这篇文章收集了我在Python新手开发者写的代码中所见到的不规范但偶尔又很微妙的问题。 本文的目的是为了帮助那些新手开发者渡...

3547
来自专栏程序员互动联盟

【专业技术】C++里面重要的几个关键字的用法

编者按: 这几个关键字非常重要,程序中经常见到他们的身影,但是确切意思有时候还需要多搜索下才能知道。笔者这里把它搬出来,也是希望大家引起重视,努力掌握它。 C+...

3607
来自专栏angularejs学习篇

js中对arry数组的各种操作小结

  最近工作比较轻松,于是就花时间从头到尾的对js进行了详细的学习和复习,在看书的过程中,发现自己平时在做项目的过程中有很多地方想得不过全面,写的不够合理,所以...

1382
来自专栏北京马哥教育

Python中下划线的5种含义

来源:Python程序员 ID:pythonbuluo 本文介绍了Python中单下划线和双下划线("dunder")的各种含义和命名约定,名称修饰(name...

3567
来自专栏java一日一条

19 个 JavaScript 编码小技巧

这篇文章适合任何一位基于JavaScript开发的开发者。我写这篇文章主要涉及JavaScript中一些简写的代码,帮助大家更好理解一些JavaScript的基...

904

扫码关注云+社区