503 Next Greater Element II

https://leetcode.com/problems/next-greater-element-ii/

solution

• 单调栈

  • 循环数组的应对方式

class Solution:
    def nextGreaterElements(self, nums: List[int]) -> List[int]:
        n = len(nums)
        res = [-1] * n
        stack = []

        for i in range(2 * n):  # 走两轮
            num = nums[i % n]
            while stack and nums[stack[-1]] < num:
                index = stack.pop()
                res[index] = num
            
            stack.append(i % n)  # option: i < n时才append
        return res

时间复杂度：O(n) 空间复杂度：O(n)