This is from Leetcode 496.

Topic request

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

Tip:

1 <= nums1.length <= nums2.length <= 1000 0 <= nums1[I], nums2[I] <= 104 Nums1 and nums2 are differentCopy the code

Their thinking

The problem can be solved by loop nesting or monotonic stack

The code shown

Method 1: violent solution

var nextGreaterElement = function(nums1, nums2) {
  const len1 = nums1.length;
  const len2 = nums2.length;
  const res = new Array(len1).fill(-1);
  for(let i = 0; i < len1; i++) {
    let index = nums2.indexOf(nums1[i]);
    while (index < len2) {
      if (nums2[index] > nums1[i]) {
        res[i] = nums2[index];
        break;
      }
      index++;
    }
  }
  return res;
};
Copy the code

The time complexity of the violent solution is O(Mn) and O(n).

Method two: monotone stack solution

var nextGreaterElement = function(nums1, nums2) { const len1 = nums1.length; const len2 = nums2.length; const map = new Map(); const stack = []; const res = []; For (let I = 0; i < len2; i++) { const t = nums2[i]; // The while loop is responsible for the comparison, and the operation of the stack is found, Set key->value while(stack.length && t > stack[stack.length - 1]) {const top = stack.pop(); map.set(top, t); } stack.push(t); } for(let i = 0; i < len1; i++) { const val = map.get(nums1[i]); res[i] = val ? val : -1; } return res; };Copy the code

The time complexity of monotone stack solution is O(m+n) and the space complexity is O(m).

conclusion

The monotone stack solution will iterate over the two arrays one by one without repeating the loop. Obviously, this method performs better.