496

class Solution:
    def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:

        st = []
        next_gt = dict()

        for num in nums2:
            while st and num > st[-1]:
                x = st.pop()
                next_gt[x] = num
            st.append(num)

        return [next_gt.get(elem, -1) for elem in nums1]