The topic of dry

You are given two arrays with no duplicate elements, nums1 and nums2, where nums1 is a subset of nums2.

Find the next value greater in nums2 for each element in nums1.

The next larger element of the number x in nums1 is the first larger element of x to the right of the corresponding position in nums2. If no, -1 is displayed at the corresponding position.

Example 1:

Input: nums1 = [4,1,2], nums2 = [1,3,4,2]. For the number 4 in num1, you cannot find the next larger number in the second array, so print -1. For the number 1 in num1, the next large number to the right of the number 1 in the second array is 3. For the number 2 in num1, there is no next larger number in the second array, so -1 is output.Copy the code

Example 2:

Input: nums1 = [2,4], nums2 = [1,2,3,4]. For the number 2 in num1, the next large number in the second array is 3. For the number 4 in num1, there is no next larger number in the second array, so -1 is output.Copy the code

Source: LeetCode link: leetcode-cn.com/problems/ne… Copyright belongs to the Collar buckle network. Commercial reprint please contact official authorization, non-commercial reprint please indicate the source.

Solution: stack +Map

Our solution to this problem is to cycle NUMs2, calculate the possible result sets of NUMS2 in turn, and put them into Map.

We can simulate the access process with this set of test cases:

Nums1 = [1, 2], nums2 = [1,3,4,2]. The first step is to iterate, there are no elements on the stack. Put 1 on the stack when iterating through 1; Key =1, value=3 in map; key=1, value=3 in map; If 4> top element 4 is found when 3 is pushed on the stack to 4, the top element is popped up and key=3, value=4 is accessed in map. When 4 is pushed to 2, 2 is less than the top element 2. When 2 is pushed to 2, there are only 4 and 2 left in the stack. Then, they are placed in the map in sequence. Finally, we match the values in the map to our target arrayCopy the code

Code implementation:

/ * * *@param {number[]} nums1
 * @param {number[]} nums2
 * @return {number[]}* /
var nextGreaterElement = function (nums1, nums2) {
    let stack = [];
    let map = new Map(a); nums2.map((item) = > {
        while(stack.length ! =0 && stack[stack.length - 1] < item) {
            let pop = stack.pop();
            map.set(pop, item)
        }
        stack.push(item)
    })
    while(stack.length ! =0) {
        let pop = stack.pop();
        map.set(pop, -1)}let newArr=new Array(nums1.length)
    nums1.map((item,index) = >{
        newArr[index]=map.get(item)
    })
    return newArr
};
Copy the code