这是悦乐书的第244次更新，第257篇原创
01 看题和准备
今天介绍的是LeetCode算法题中Easy级别的第111题（顺位题号是496）。你有两个数组（没有重复）nums1和nums2，其中nums1的元素是nums2的子集。在nums2的相应位置找到nums1元素的所有下一个更大的数字。nums1中的数字x的下一个更大数字是nums2中右边第一个更大的数字。如果它不存在，则输出该数字的-1。例如：
输入：nums1 = [4,1,2]，nums2 = [1,3,4,2]。
输出：[-1,3,-1]
说明：对于第一个数组中的数字4，在第二个数组中找不到下一个更大的数字，因此输出-1。对于第一个数组中的数字1，第二个数组中的下一个更大数字是3。对于第一个数组中的数字2，第二个数组中没有下一个更大的数字，因此输出-1。
输入：nums1 = [2,4]，nums2 = [1,2,3,4]。
输出：[3,-1]
说明：对于第一个数组中的数字2，第二个数组中的下一个更大数字是3。对于第一个数组中的数字4，第二个数组中没有下一个更大的数字，因此输出-1。
注意：
nums1和nums2中的所有元素都是唯一的。
nums1和nums2的长度不会超过1000。
本次解题使用的开发工具是eclipse，jdk使用的版本是1.8，环境是win7 64位系统，使用Java语言编写和测试。
02 第一种解法
暴力解法。使用两层循环，先找到nums1的元素在nums2中的对应元素，然后从nums2中找到的元素的下一位往右开始判断，找到比当前元素大的元素，找得到就将其作为结果数组的元素添加进去，否则就将-1添加进结果数组。
public int[] nextGreaterElement(int[] nums1, int[] nums2) {
int[] result = new int[nums1.length];
for (int i=0; i<nums1.length; i++) {
int j = 0, k = 0;
for (; j<nums2.length; j++) {
if (nums1[i] == nums2[j]) {
break;
}
}
for (k = j+1; k<nums2.length; k++) {
if (nums2[k] > nums2[j]) {
result[i] = nums2[k];
break;
}
}
if (k == nums2.length) {
result[i] = -1;
}
}
return result;
}
03 第二种解法
我们可以将第一种方法进行优化，将nums2中的元素作为key、索引作为value存入HashMap，在原来第一种解法中每次通过循环来定位nums2中的索引位置，换成了通过key查找value的映射，获取到索引后，从索引后一位开始依次寻找比nums1的当前元素大的数字，找得到就替换已经设值为-1的结果数组的元素值。
public int[] nextGreaterElement2(int[] nums1, int[] nums2) {
int[] result = new int[nums1.length];
Map<Integer, Integer> map = new HashMap<Integer, Integer>();
for (int i=0; i<nums2.length; i++) {
map.put(nums2[i], i);
}
for (int j=0; j<nums1.length; j++) {
result[j] = -1;
int index = map.get(nums1[j]);
for (int k = index + 1; k<nums2.length; k++) {
if (nums2[k] > nums1[j]) {
result[j] = nums2[k];
break;
}
}
}
return result;
}
04 第三种解法
使用HashMap和栈。在第二种解法中我们使用HashMap存的是nums2的值、索引，在此解法中，我们使用HashMap存的是，如果nums2的当前元素存在右边最大数，上一个元素为key，当前元素为value。
在遍历nums2中的元素时，如果栈不为空，并且当前栈顶的值小于当前元素，即nums2的前一个元素存在右边最大数，此时，我们需要将栈顶的元素作为key，当前元素作为value，存入HashMap中，同时，要将栈顶的元素移除，此操作是循环执行的。最后我们再将nums2的当前元素存入stack中。
接着，我们要开始处理nums1的数据了，遍历其中的元素，如果能够在HashMap中找到对应的值，就取其value作为结果数组的元素值，否则取-1作为默认值。
public int[] nextGreaterElement3(int[] nums1, int[] nums2) {
int[] result = new int[nums1.length];
Map<Integer, Integer> map = new HashMap<Integer, Integer>();
Stack<Integer> stack = new Stack<Integer>();
for (int num : nums2) {
while (!stack.isEmpty() && stack.peek() < num) {
map.put(stack.pop(), num);
}
stack.push(num);
}
for (int i=0; i<nums1.length; i++) {
result[i] = map.getOrDefault(nums1[i], -1);
}
return result;
}
05 小结
算法专题目前已日更超过三个月，算法题文章111+篇，公众号对话框回复【数据结构与算法】、【算法】、【数据结构】中的任一关键词，获取系列文章合集。
以上就是全部内容，如果大家有什么好的解法思路、建议或者其他问题，可以下方留言交流，点赞、留言、转发就是对我最大的回报和支持！