# 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。

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

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;
}

3、改进：

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;
}

202 篇文章43 人订阅

0 条评论

## 相关文章

3344

923

2025

4688

### es6 Object的几个新方法

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

1013

3547

3607

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

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

1382

3567

904