496. The next bigger element I

The title

Given two arrays nums1 and nums2 with no repeating elements, nums1 is a subset of nums2. Find the next value of each element in nums1 that is greater than nums2. 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

Note:

  1. All elements in nums1 and nums2 are unique.
  2. The array size of nums1 and nums2 cannot exceed 1000.

Train of thought

Monotonic stack + hash map

/** * @desc monotone stack + hash map, * time complexity: O(M+N), where M and N are the lengths of nums1 and nums2 respectively. Because the two of us cycle. * Space complexity: O(N). As we traverse NUMs2, we need to use a stack, along with a hash map, to temporarily store answers. * @param {number[]} nums1 * @param {number[]} nums2 * @return {number[]} */
var nextGreaterElement = function(nums1, nums2) {
    if (Array.isArray(nums1) && Array.isArray(nums2)) {
        // 1. Iterate over nusm2 to find the next larger element value for each element in nusm2 and put its mapping into a hash map
        // 2. Rules for comparison during traversal: when the stack is empty, the element behind the stack is compared with the element at the top of the stack. If the element behind the stack is always larger than the element at the top of the stack, the element is removed from the stack and the corresponding mapping is stored in the map
        // 3. Check whether the stack is empty. If it is not empty (there is no next larger element), iterate out the elements in the stack and set the corresponding mapping relationship to save to map.
        // 4. Iterate over nusM1 and return the mapping in map
        const result = []
        const stack = []
        const map = new Map(a)for (let i = 0; i < nums2.length; i++) {
            if(! stack.length) { stack.push(nums2[i]) }else {
                while (nums2[i] > stack[stack.length - 1]) {
                    map.set(stack.pop(), nums2[i])
                }
                stack.push(nums2[i])
            }
        }
        while(stack.length) {
            map.set(stack.pop(), - 1)}for (let i = 0; i < nums1.length; i++) {
            result.push(map.get(nums1[i]))
        }
        return result
    }
};
Copy the code

advertising

If you think it’s interesting, click on the lower right corner, or pay attention to it directly.