[Daily LeetCode] 496. Next Greater Element I

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.

Solution with efficiency:

 

class Solution(object):
    def nextGreaterElement(self, findNums, nums):
        """
        :type findNums: List[int]
        :type nums: List[int]
        :rtype: List[int]
        """

        d = {}
        ans = [-1] * len(findNums)
        for i, num in enumerate(findNums):
            d[num] = i
        stack = []
        for num in nums:
            while stack and stack[-1] < num:
                top = stack.pop()
                if top in d:
                    ans[d[top]] = num
            stack.append(num)
        return ans

Analysis

We have to specify in which cases shall we change the number in ans:[-1, -1,….]: we do not have to change the number when the next number in nums is smaller then the previous number, we do not have to change the ans when the next greater number is not in findNums. Vice versa, apart from the occasion stated, we have to change the number

Leave a Reply

Your email address will not be published. Required fields are marked *