## 题目描述

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.

## 解法一

### 思路

1. `nums2`中找到`num1`的下标`index`
2. `nums2`的(`index`, `len(nums2)`)范围内找到第一个比`num1`大的数。

### Python

``````class Solution(object):
def nextGreaterElement(self, findNums, nums):
"""
:type findNums: List[int]
:type nums: List[int]
:rtype: List[int]
"""
result = []
if not findNums:
return result
num_max = max(nums)
map = [-1] * (num_max + 1)
for index, num in enumerate(nums):
map[num] = index
for find_num in findNums:
if find_num >= num_max:
result.append(-1)
else:
current_index = map[find_num] + 1
while current_index < len(nums):
if nums[current_index] > find_num:
result.append(nums[current_index])
break
current_index += 1
if current_index == len(nums):
result.append(-1)
return result``````

### Java

``````public class Solution {
public int[] nextGreaterElement(int[] findNums, int[] nums) {
if (findNums.length == 0) {
return new int[]{};
}
int numMax = -1;
for (int num : nums) {
if (num > numMax) {
numMax = num;
}
}
int[] map = new int[numMax + 1];
for (int i = 0; i < nums.length; i++) {
map[nums[i]] = i;
}
int[] result = new int[findNums.length];
for (int i = 0; i < findNums.length; i++) {
int currentNum = findNums[i];
if (currentNum > numMax) {
result[i] = -1;
} else {
int currentIndex = map[currentNum] + 1;
while (currentIndex < nums.length) {
if (nums[currentIndex] > currentNum) {
result[i] = nums[currentIndex];
break;
}
currentIndex++;
}
if (currentIndex == nums.length) {
result[i] = -1;
}
}
}
return result;
}
}``````

### C++

``````class Solution {
public:
vector<int> nextGreaterElement(vector<int> &findNums, vector<int> &nums) {
vector<int> result;
if (findNums.empty()) {
return result;
}
int numMax = *max_element(nums.begin(), nums.end());
vector<int> map(numMax + 1, 0);
for (int i = 0; i < nums.size(); i++) {
map[nums[i]] = i;
}
for (int i = 0; i < findNums.size(); i++) {
int currentNum = findNums[i];
if (currentNum > numMax) {
result.push_back(-1);
} else {
int currentIndex = map[currentNum] + 1;
while (currentIndex < nums.size()) {
if (nums[currentIndex] > currentNum) {
result.push_back(nums[currentIndex]);
break;
}
currentIndex++;
}
if (currentIndex == nums.size()) {
result.push_back(-1);
}
}
}
return result;
}
};``````