E-496. Next Greater Element I

Loading...LeetCode

# O(n+m), O(n+m). 这里用到了一个比较有意思的数据结构, 单调栈, 即monotonous stack.
# 保持stack里面数据的单调性(大于/小于peak的才被压入)
class Solution:
    def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
        mono_stack = []
        res_map = {}
        for num in nums2:
            while mono_stack and mono_stack[-1] < num:
                res_map[mono_stack.pop()] = num
            mono_stack.append(num)
                        
        while mono_stack:
            res_map[mono_stack.pop()] = -1

        res_lst = []
        for num in nums1:
            res_lst.append(res_map[num])
            
        return res_lst