即日起在codingBlog上分享您的技术经验即可获得积分,积分可兑换现金哦。

Next Greater Element I

编程语言 pkmifeng 28℃ 0评论
本文目录
[隐藏]

1.Next Greater Element I

1.1.1.problem:

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.

1.1.2.thinking:

采用一个map来记录数组二中每个元素和他右边第一个比他大的元素的对应关系.那么对于数组一,只需要在map中进行寻找即可.构造map的时候,也需要双重循环,但是内层循环可以从每次的元素之后开始循环,时间复杂度可以降低为O(log2n)。

1.1.3.solution:

class Solution {
public:
    vector<int> nextGreaterElement(vector<int>& findNums, vector<int>& nums) {
        vector<int> ret;
        unordered_map<int, int> m;
        for (int i=0; ifor (int j = i;jif (nums[i]break;
                }
            }
        for (int i=0; icout(findNums[i])? m[findNums[i]] : -1);
        return ret;
    }
};

转载请注明:CodingBlog » Next Greater Element I

喜欢 (0)or分享 (0)
发表我的评论
取消评论

*

表情