（题目来源:力扣LeetCode)
题目：给你两个 没有重复元素 的数组 nums1 和 nums2 ，其中nums1 是 nums2 的子集。
请你找出 nums1 中每个元素在 nums2 中的下一个比其大的值。
nums1 中数字 x 的下一个更大元素是指 x 在 nums2 中对应位置的右边的第一个比 x 大的元素。如果不存在，对应位置输出 -1 。
示例 1
输入: nums1 = [4,1,2], nums2 = [1,3,4,2].
输出: [-1,3,-1]
解释:
对于 num1 中的数字 4 ，你无法在第二个数组中找到下一个更大的数字，因此输出 -1 。
对于 num1 中的数字 1 ，第二个数组中数字1右边的下一个较大数字是 3 。
对于 num1 中的数字 2 ，第二个数组中没有下一个更大的数字，因此输出 -1 。
方法一：暴力解法
题解：
1、先找出在nums2中与num1s中先对应的元素的索引
2、从该元素的索引往后遍历，找到第一个大于该元素的数，如果没有找到就返回-1
classSolution{
public int[] nextGreaterElement(int[] nums1, int[] nums2) {
int[] array = new int[nums1.length];
for(int i=0;i<nums1.length;i++){
int j=0;
while(nums1[i]!=nums2[j])
j++;
for(int k=j+1;k<=nums2.length;k++){
if(k>=nums2.length){
array[i]=-1;
break;
}
if(nums2[k]>nums2[j]){
array[i]=nums2[k];
break;
}
}
}
return array;
}
}
时间复杂度：O（MN），M、N分别是两个数组的长度
方法二：单调栈+哈希表
题解：
1、先遍历nums2，并且寻找nums2中每个元素后面第一个比本元素大的元素。
2、在遍历的过程中，将每一个元素入栈，如果遇到了后一个比栈顶元素大的值，就将栈顶元素出栈、比栈顶元素大的值入栈，并且将栈顶元素作为键（Key），比栈顶元素大的元素作为值（Value）存入哈希表中。如果后一个元素比栈顶元素小，那么栈顶元素不动，后一个元素压栈，直到遇到了一个元素比当前的栈顶元素大，那么栈顶元素出栈、比栈顶元素大的值入栈，并且将栈顶元素作为键（Key），比栈顶元素大的元素作为值（Value）存入哈希表中。
3、遍历nums1，并且访问哈希表，得到每一个与nums2相应的元素的哈希值（其实就是后一个最大元素），如果有元素找不到哈希值，就代表它没有下一个更大元素，返回-1
public int[] nextGreaterElement(int[] nums1, int[] nums2) {
int len1 = nums1.length;
int len2 = nums2.length;
Deque<Integer> stack = new ArrayDeque<>();
Map<Integer,Integer> map = new HashMap<>();
//先判断num2,把对应关系存入哈希表 for(int i=0;i<len2;i++){
while(!stack.isEmpty() && stack.peekLast()<nums2[i]){
map.put(stack.removeLast(),nums2[i]);
}
stack.addLast(nums2[i]);
}
int [] res = new int [len1];
//在遍历num1 for(int i =0;i<len1;i++){
res[i]=map.getOrDefault(nums1[i],-1);
}
return res;
}
