[LeetCode] 496. Next Greater Element I 下一个较大的元素 I

我会带着你远行 2022-10-02 12:52 128阅读 0赞

You are given two arrays (without duplicates) `nums1` and `nums2 `where `nums1`’s elements are 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, output -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.

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.

Note:

1.  All elements in `nums1` and `nums2` are unique.
2.  The length of both `nums1` and `nums2` would not exceed 1000.

解法：栈，递减栈。先求出nums2中所有元素的右边第一个较大数字的位置，并记录到map中。然后，因为nums1是子数组，循环nums1中的元素，记录在map中值并返回。求nums2中下一个较大元素时用递减栈，循环元素，当前元素大于栈顶元素时，就弹出栈顶元素，并记录栈顶元素下一个最大就是当前元素。然后继续比较栈顶元素，直到小于或等于栈顶元素。

python代码：

class Solution(object):
        def nextGreaterElement(self, findNums, nums):
            """
            :type findNums: List[int]
            :type nums: List[int]
            :rtype: List[int]
            """
            d = {}
            st = []
            ans = []
             
            for x in nums:
                while len(st) and st[-1] < x:
                    d[st.pop()] = x
                st.append(x)
     
            for x in findNums:
                ans.append(d.get(x, -1))
                 
            return ans