地址
难度
简单
题目
nums1 中数字 x 的 下一个更大元素 是指 x 在 nums2 中对应位置 右侧 的 第一个 比 x 大的元素。给你两个 没有重复元素 的数组 nums1 和 nums2 ，下标从 0 开始计数，其中nums1 是 nums2 的子集。
对于每个 0 <= i < nums1.length ，找出满足 nums1[i] == nums2[j] 的下标 j ，并且在 nums2 确定 nums2[j] 的 下一个更大元素 。如果不存在下一个更大元素，那么本次查询的答案是 -1 。
返回一个长度为 nums1.length 的数组 ans 作为答案，满足 ans[i] 是如上所述的 下一个更大元素 。
示例 1：
输入：nums1 = [4,1,2], nums2 = [1,3,4,2].
输出：[-1,3,-1]
解释：nums1 中每个值的下一个更大元素如下所述：
-
4 ， 用加粗斜体标识，nums2 = [1,3,4,2]。不存在下一个更大元素，所以答案是 -1 。
-
1 ，用加粗斜体标识，nums2 = [1,3,4,2]。下一个更大元素是 3 。
-
2 ，用加粗斜体标识，nums2 = [1,3,4,2]。不存在下一个更大元素，所以答案是 -1 。
示例 2：
输入：nums1 = [2,4], nums2 = [1,2,3,4].
输出：[3,-1]
解释：nums1 中每个值的下一个更大元素如下所述：
-
2 ，用加粗斜体标识，nums2 = [1,2,3,4]。下一个更大元素是 3 。
-
4 ，用加粗斜体标识，nums2 = [1,2,3,4]。不存在下一个更大元素，所以答案是 -1 。
提示：
* 1 <= nums1.length <= nums2.length <= 1000
* 0 <= nums1[i], nums2[i] <= 10^4
* nums1和nums2中所有整数 互不相同
* nums1 中的所有整数同样出现在 nums2 中
进阶:
你可以设计一个时间复杂度为 O(nums1.length + nums2.length) 的解决方案吗？
思路
对于这类题目可以使用单调栈方法
该方法采用先行将 nums2 中的数字，对应的下一个更大的数字已经找出来，然后放到哈希表中，以供后面 nums1直接使用即可，我们这样做，可以将时间复杂度降到 n+m。
具体流程如下：
-
创建一个临时栈，一个哈希表，然后遍历 nums2
-
若当前栈无数据，则当前数字入栈备用。
-
若当前栈有数据，则用当前数字与栈顶比较：
- 当前数字 > 栈顶，代表栈顶对应下一个更大的数字就是当前数字，则将该组数字对应关系，记录到哈希表。
- 当前数字 < 栈顶，当前数字压入栈，供后续数字判断使用。
-
这样，就可以看到哈希表中存在部分 nums2 数字的对应关系了，而栈中留下的数字，代表无下一个更大的数字，全部赋值为 −1，然后存入哈希表即可。
-
遍历 nums1，直接询问哈希表拿对应关系即可。
class Solution {
public int[] nextGreaterElement(int[] nums1, int[] nums2) {
int len1 = nums1.length;
int len2 = nums2.length;
Deque<Integer> deque =new ArrayDeque<>();
HashMap<Integer, Integer> hashMap = new HashMap<>();
for (int i = 0; i < len2; i++) {
while (!deque.isEmpty() && deque.peekLast()<nums2[i]){
hashMap.put(deque.removeLast(),nums2[i]);
}
deque.add(nums2[i]);
}
int[] res =new int[len1];
for(int i=0;i<len1;i++){
res[i] = hashMap.getOrDefault(nums1[i],-1);
}
return res;
}
}