给定一个循环数组（最后一个元素的下一个元素是数组的第一个元素），输出每个元素的下一> 个更大元素。数字 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
