503. 下一个更大元素 II

给定一个循环数组（最后一个元素的下一个元素是数组的第一个元素），输出每个元素的下一> 个更大元素。数字 x 的下一个更大的元素是按数组遍历顺序，这个数字之后的第一个比它更大> 的数，这意味着你应该循环地搜索它的下一个更大的数。如果不存在，则输出 -1。

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

对于这一类的题目，第一想法就是递增/减栈。只需要扫描一遍数组，当前循环数字比栈顶元素小就入栈，否则就将栈顶元素出栈，直到栈顶元素大于当前数字。而所有当前循环里出栈的元素的下一个更大元素就是当前循环元素。

另外需要注意的点是，因为这是一个循环数组，所以下一个更大元素的下标可能小于当前下标。一个简单的处理方法是重复给定的数组两遍，如果扫描数组两遍后没有找到下一个更大元素，那必定不存在（其实也就是数组中的最大值）。因为需要维护一个栈，所以空间复杂度是O(n)，对于时间复杂度，因为每一个元素至多入栈、出栈各一次，所以时间复杂度应该也是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