发表于 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

• LC 题目链接