• Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”.
  • This article has participated in the “Digitalstar Project” and won a creative gift package to challenge the creative incentive money.

Leetcode -496- Next larger element I

[Blog link]

The path to learning at 🐔

The nuggets home page

[答 案]

Topic link

[making address]

Making the address

[B].

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
  • All integers in nums1 and nums2 are different
  • All integers in nums1 also appear in nums2

 

Advanced: Can you design a time complexity O(nums1.length + nums2.length) solution?

Idea 1: violent search

  • The simplest is definitely a violent search
  • Just do it once for every round
public int[] nextGreaterElement(int[] nums1, int[] nums2) {
    int m = nums1.length, n = nums2.length;
    int[] res = new int[m];
    for (int i = 0; i < m; ++i) {
        int j = 0;
        while(j < n && nums2[j] ! = nums1[i]) { ++j; }int k = j + 1;
        while (k < n && nums2[k] < nums2[j]) {
            ++k;
        }
        res[i] = k < n ? nums2[k] : -1;
    }
    return res;
}
Copy the code
  • Time complexity O(m* N)
  • Space complexity O(1)

Idea 2: monotone stack

  • Store numS2 elements in reverse order on the monotonic stack
  • Records each element’s closest element greater than itself
  • If you don’t have one, you put minus one
public int[] nextGreaterElement(int[] nums1, int[] nums2) {
    Map<Integer, Integer> map = new HashMap<>();
    Stack<Integer> stack = new Stack<>();
    for (int i = nums2.length-1; i >= 0; i--) {
        int x = nums2[i];
        while(! stack.isEmpty() && stack.peek() <= x) { stack.pop(); } map.put(x, stack.isEmpty() ? -1 : stack.peek());
        stack.push(x);
    }
    int[] res = new int[nums1.length];
    for (int i = 0; i < res.length; i++) {
        res[i] = map.get(nums1[i]);
    }
    return res;
}
Copy the code
  • Time complexity O(m+ N)
  • Space complexity O(n)