JZX轻语：简
LeetCode 503 - 下一个更大元素II
发表于2024年06月24日
单调栈模板题，差异点在于循环数组。我们可以将数组复制一份，然后将其拼接到原数组的后面，这样就可以将循环数组转化为普通数组。然后按照单调栈的模板进行处理即可。
class Solution:
def nextGreaterElements(self, nums: List[int]) -> List[int]:
ans = [-1] * len(nums)
stack = []
for i in range(len(nums) * 2):
num = nums[i % len(nums)]
while stack and nums[stack[-1] % len(nums)] < num:
ans[stack[-1] % len(nums)] = num
stack.pop()
stack.append(i)
return ans可以考虑优化点：两次循环列表(其中第二次循环不再将元素加入到栈中)，当第二次循环时，栈顶元素的位置小于等于当前位置时，意味着栈内所有的元素(其位置必然均小于等于栈顶元素的位置)已经找不到更大的元素，直接跳出循环即可。缺点是需要多写一次循环的代码。
class Solution:
def nextGreaterElements(self, nums: List[int]) -> List[int]:
ans = [-1] * len(nums)
stack = []
# 第一次循环就是单调栈的模板
for i, num in enumerate(nums):
while stack and nums[stack[-1]] < num:
ans[stack[-1]] = num
stack.pop()
stack.append(i)
# 第二次循环本质是找栈内剩余元素的下一个更大元素，这个更大元素位置如存在，必然在左边
for i, num in enumerate(nums):
if not stack or stack[-1] <= i:
break
while stack and stack[-1] > i and nums[stack[-1]] < num:
ans[stack[-1]] = num
stack.pop()
return ans