Title address (496. Next larger element I)

Leetcode-cn.com/problems/ne…

Topic describes

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: enter 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. Example 2: enter 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. Tip:  1 <= nums1.length <= nums2.length <= 1000 0 <= nums1[i], Nums2 [I] <= 104 Nums1 [I] <= 104 Nums1 [I] <= 104 Nums1 [I] <= 104Copy the code

Train of thought

Use a monotonic stack to hold the maximum right value, and then use a dictionary to hold the maximum right value for each element

code

  • Language support: Python3

Python3 Code:


class Solution:
    def nextGreaterElement(self, nums1: List[int], nums2: List[int]) - >List[int] :
        resDict = dict()
        stack = list(a)Use monotone stack to store the maximum value first in reverse order
        for i in nums2[::-1] :There is a value in the stack, which means there is a large value to the right of the target
            while len(stack)>0:
                # check if the value on the right is larger than itself, save the result if it is larger, otherwise pop
                if stack[-1]>i:
                    resDict[i] = stack[-1]
                    break
                else:
                    stack.pop()
            # throw itself on the stack
            stack.append(i)
            # If you don't find one bigger than yourself, save it by -1
            if i not in resDict:resDict[i] = -1
        res = list(a)for j in nums1:
            res.append(resDict[j])
        return res

if __name__ == '__main__':
    nums1 = [4.1.2]
    nums2 = [1.3.4.2]
    nums1 = [2.4]
    nums2 = [1.2.3.4]
    result = Solution().nextGreaterElement(nums1,nums2)
    print(result)

Copy the code

Complexity analysis

Let n be the length of the array.

  • Time complexity: O(n)O(n)O(n)
  • Space complexity: O(n)O(n)O(n)