給定一個循環(huán)數(shù)組（最后一個元素的下一個元素是數(shù)組的第一個元素），輸出每個元素的下一> 個更大元素。數(shù)字 x 的下一個更大的元素是按數(shù)組遍歷順序，這個數(shù)字之后的第一個比它更大> 的數(shù)，這意味著你應(yīng)該循環(huán)地搜索它的下一個更大的數(shù)。如果不存在，則輸出 -1。

輸入: [1,2,1]
輸出: [2,-1,2]

對于這一類的題目，第一想法就是遞增/減棧。只需要掃描一遍數(shù)組，當(dāng)前循環(huán)數(shù)字比棧頂元素小就入棧，否則就將棧頂元素出棧，直到棧頂元素大于當(dāng)前數(shù)字。而所有當(dāng)前循環(huán)里出棧的元素的下一個更大元素就是當(dāng)前循環(huán)元素。

另外需要注意的點是，因為這是一個循環(huán)數(shù)組，所以下一個更大元素的下標(biāo)可能小于當(dāng)前下標(biāo)。一個簡單的處理方法是重復(fù)給定的數(shù)組兩遍，如果掃描數(shù)組兩遍后沒有找到下一個更大元素，那必定不存在（其實也就是數(shù)組中的最大值）。因為需要維護一個棧，所以空間復(fù)雜度是O(n)，對于時間復(fù)雜度，因為每一個元素至多入棧、出棧各一次，所以時間復(fù)雜度應(yīng)該也是O(n)。

參考代碼：

class Solution:
    def nextGreaterElements(self, nums: List[int]) -> List[int]:
        # initialization
        result = [-1] * len(nums)
        decreaseStack = list()

        for idx, val in enumerate(nums * 2):
            if len(decreaseStack) == 0 or val <= nums[decreaseStack[-1]]:
                # if current number is no greater than the number
                # sitting on top of the stack, just push it into
                # the stack
                decreaseStack.append(idx % len(nums))
            else:
                # pop the numbers from the stack while they are smaller
                # than current number, and mark them in the result array
                while len(decreaseStack) > 0 and val > nums[decreaseStack[-1]]:
                    poppedIdx = decreaseStack.pop()
                    result[poppedIdx] = val
                decreaseStack.append(idx % len(nums))

        return result