下一个更大元素I-栈496-python

没看答案，暴力解法，时间复杂度O(n^2)。

class Solution:
    def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
        res = []
        
        for i in nums1:
            pos = nums2.index(i)
            for num in nums2[pos:]:
                if num > i:
                    res.append(num)
                    break
            else:
                res.append(-1)
        
        return res

单调栈解法，时间复杂度O(n)。

class Solution:
    def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:      
        stack = []
        m, n = len(nums1), len(nums2)
        pos = {}
        res = [0] * m

        for idx, num in enumerate(nums1):
            pos[num] = idx

        for i in range(n-1, -1, -1):
            while stack and stack[-1] <= nums2[i]:
                stack.pop()

            if nums2[i] in pos.keys():
                if not stack:
                    res[pos[nums2[i]]] = -1
                else:
                    res[pos[nums2[i]]] = stack[-1]
            stack.append(nums2[i])
        
        return res