This article is participating in Python Theme Month. See the link to the event for more details

describe

You are given two integer arrays nums1 and nums2 both of unique elements, where nums1 is a subset of nums2.

Find all the next greater numbers for nums1’s elements in the corresponding places of nums2.

The Next Greater Number of a number x in nums1 is the first greater number to its right in nums2. If it does not exist, return -1 for this number.

Example 1:

Input: nums1 = [4,1,2], nums2 = [1,3,4,2]
Output: [-1,3,-1]
Explanation:
For number 4 in the first array, you cannot find the next greater number for it in the second array, so output -1.
For number 1 in the first array, the next greater number for it in the second array is 3.
For number 2 in the first array, there is no next greater number for it in the second array, so output -1.
Copy the code

Example 2:

Input: nums1 = [2,4], nums2 = [1,2,3,4]
Output: [3,-1]
Explanation:
For number 2 in the first array, the next greater number for it in the second array is 3.
For number 4 in the first array, there is no next greater number for it in the second array, so output -1.
Copy the code

Note:

1 <= nums1.length <= nums2.length <= 1000
0 <= nums1[i], nums2[i] <= 10^4
All integers in nums1 and nums2 are unique.
All the integers of nums1 also appear in nums2.
Copy the code

parsing

Num1 is a subset of num2. Find the first number larger than num1 after the corresponding position of each element in num2. If there is none, the result is -1. I have defined a method find to find a number larger than nums2[idx] after the idx position in num2. I iterate directly over NUM1 to get the index of the element in num2, and then append the result to result using the find function I defined. At the end of the walk, I get the result.

answer

class Solution(object):
    def nextGreaterElement(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: List[int]
        """
        def find(A, idx):
            result = -1
            for i in range(idx, len(A)):
                if A[i]>A[idx]:
                    result = A[i]
                    break
            return result
        result = []
        for n in nums1:
            idx = nums2.index(n)
            result.append(find(nums2, idx))
        return result
        
        	      
		
Copy the code

The results

Runtime: 10000 ms, faster than 21.98% of Python online submissions for Next Greater Element Submissions in the linked list for Next Greater Element ICopy the code

parsing

There is also a way to use the dictionary and stack, because each nums1 number is in nums2, walk through each numS2 number, find each element and the first large element after it, store it in the dictionary D, and then walk through each num1 number, The value is received directly from D, and if not, -1 is returned directly.

answer

class Solution(object):
    def nextGreaterElement(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: List[int]
        """
        result = []
        stack = []
        d = {}
        for num in nums2:
            while len(stack) and (stack[-1]<num):
                d[stack.pop()] = num
            stack.append(num)
        for num in nums1:
            result.append(d.get(num,-1))
        return result
        
Copy the code

The results

Runtime: 10 ms, the linked list for Next Greater Element in the linked list Submissions in the linked list for Next Greater Element ICopy the code

Link: leetcode.com/problems/ne…

Your support is my greatest motivation