496. Next Greater Element I

leetcode.com/problems/next-greater-element-i/

Next Greater Element I - LeetCode

이 문제도 전형적인 스택문제

 

문제 설명이 명확하지 않아서 헷갈리는 부분이 있을 수 있는데

 

결국 num2 기준으로 각 숫자 다음에 오는 큰 숫자를 찾아놓고

num1에 각각 매핑되는 큰 숫자를 담아 리턴하는 문제다.

class Solution:
    def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
        if not nums2:
            return []
        
        memo = dict()
        memo[nums2[-1]] = -1
        stack = [nums2[-1]]
        
        for n in nums2[:-1][::-1]:
            while stack and stack[-1] <= n:
                stack.pop()
            if not stack:
                memo[n] = -1
            else:
                memo[n] = stack[-1]
                
            stack.append(n)
        
        ret = []
        for n in nums1:
            ret.append(memo[n])
        
        return ret