題目出處

496. Next Greater Element I

難度

easy

個人範例程式碼

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

        ans_hashtable = {}
        stack = []

        for num in nums2:
            while stack and stack[-1] < num: # new is greater
                ans_hashtable[stack[-1]] = num # last number's answer = this num
                del stack[-1]            
            stack.append(num)

        for rest_element in stack:
            ans_hashtable[rest_element] = -1

        return [ans_hashtable[num] for num in nums1]

算法說明

像這類有「找後續/前綴」中比較大或比較小的第一個數字，
我們通常會用 stack 來保存「等待被決定的內容」。

當我們發現「stack[-1]」<「新的數字」，表示找到答案，
我們 pop[-1] 出 stack，並記錄「 pop 的答案就是當前數字 」。

最後剩下在 stack 的內容，答案都是 -1

input handling

如果沒有 nums, 回傳 [] (題目沒特別要求)

Boundary conditions

用 for 迴圈控制範圍

Reference

• 下一个更大的数 I · Next Greater Element I