题目来源
我一开始想的是用一个哈希表来记录nums2里的每个元素的位置，然后遍历nums1，直接根据哈希表从对应位置往后遍历比较，代码如下：
class Solution {
public:
vector<int> nextGreaterElement(vector<int>& findNums, vector<int>& nums) {
int n1 = findNums.size(), n2 = nums.size();
vector<int> res(n1, -1);
unordered_map<int, int> map;
for (int i=0; i<n2; i++) {
map[nums[i]] = i;
}
for (int i=0; i<n1; i++) {
for (int j=map[findNums[i]]; j<n2; j++)
if (findNums[i] < nums[j]) {
res[i] = nums[j];
break;
}
}
return res;
}
};
然后看了答案，只需要O(n)的方法就可以了，就是设置一个栈，遍历nums2，进栈使得栈中是递减序列，假如出现一个大的，就把栈中小的出栈并且记录在map中，刚才出列的那些元素后面大的元素就是刚进栈的那个。
而且不需要另外设置一个nums1大小的空间，直接用就可以了。
代码如下：
class Solution {
public:
vector<int> nextGreaterElement(vector<int>& findNums, vector<int>& nums) {
int n1 = findNums.size(), n2 = nums.size();
unordered_map<int, int> map;
stack<int> s;
for (int i=0; i<n2; i++) {
while (!s.empty() && nums[i] > s.top()) {
int tmp = s.top();
map[tmp] = nums[i];
s.pop();
}
s.push(nums[i]);
}
for (int i=0; i<n1; i++) {
if (map.find(findNums[i]) != map.end())
findNums[i] = map[findNums[i]];
else
findNums[i] = -1;
}
return findNums;
}
};
