503.|503. 下一个更大元素 II 503.下一个更大元素II

给定一个循环数组（最后一个元素的下一个元素是数组的第一个元素），输出每个元素的下一> 个更大元素。数字 x 的下一个更大的元素是按数组遍历顺序，这个数字之后的第一个比它更大> 的数，这意味着你应该循环地搜索它的下一个更大的数。如果不存在，则输出 -1。
【503.|503. 下一个更大元素 II】输入: [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