滨州的网站开发,写论文的网站,江西省注册和城乡建设厅网站,外贸网建站题目#xff1a;
nums1 中数字 x 的 下一个更大元素 是指 x 在 nums2 中对应位置 右侧 的 第一个 比 x 大的元素。 给你两个 没有重复元素 的数组 nums1 和 nums2 #xff0c;下标从 0 开始计数#xff0c;其中nums1 是 nums2 的子集。 对于每个 0 i nums1.lengt…题目
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] 是如上所述的 下一个更大元素 。
分析
这道题目最直接的思路就是俩次for循环遍历nums2找到第一个比当前元素大的值存入map然后遍历nums1即可 还有一种办法可以不用俩次for循环遍历nums2我们想一下俩次遍历nums2的目的就是因为有可能比当前元素最大的那个值还在后面在当下的遍历没办法确定下来这种时候就要想到一个数据结构即栈栈可以先暂时把不确定的元素存起来
import java.util.Map;
import java.util.HashMap;
import java.util.Deque;
import java.util.LinkedList;public class nextGreaterElementI {public static void main(String[] args) {int[] arr {4,1,2};int[] brr {1,3,4,2};int[] crr getNextMax(arr,brr);for(int i 0;icrr.length;i) {System.out.println(crr[i]);}}public static int[] getNextMax(int[] arr,int[] brr) {Map mp new HashMap();Deque stack new LinkedList();for(int i 0;ibrr.length;i) {while(stack.size() ! 0 (int) stack.peek() brr[i]) {mp.put(stack.peek(),brr[i]);stack.pop();}stack.push(brr[i]);}int[] crr new int[arr.length];int j 0;for(int i 0;iarr.length;i) {if(mp.containsKey(arr[i])) {crr[j] (int) mp.get(arr[i]);} else {crr[j] -1;}}return crr;}
}
