題目出處

503. Next Greater Element II

難度

medium

個人範例程式碼

class Solution:
    def nextGreaterElements(self, nums: List[int]) -> List[int]:
        if not nums:
            return []

        ans = [-1 for i in range(len(nums))] # default not found
        stack = []

        # first round
        for i, num in enumerate(nums):
            while stack and nums[stack[-1]] < num:
                idx = stack.pop()
                ans[idx] = num                
            stack.append(i) # push index in stack

        # sencond round, clear stack    
        for i, num in enumerate(nums):
            if not stack:
                break 
            while stack and nums[stack[-1]] < num:
                idx = stack.pop()
                ans[idx] = num                

        return ans

算法說明

• 本題的前一題為無迴圈版本，這題目的 array 為循環數組，前一題可參考：

【Leetcode】python – [496] Next Greater Element I 個人解法筆記

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

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

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

與前一題不同處

與前一題不同的地方是，因為這次題目給的 array 變成有循環 array，
因此我們只需要循環兩次即可。

在第二次循環的過程中，目標是處理掉 stack 剩下的內容，
如果最後都還處理不掉的話，就是 -1 (找不到的情況，我們 default 就先給 -1)

input handling

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

Boundary conditions

用 for 迴圈控制範圍

Reference

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