503. Next Greater Element II

Next Greater Element II - LeetCodeLeetCode

本以为 monotonic stack 应该不会经常出现，没想到相关的题目还不少...

• 要找 next xxx --> 逆序遍历

• exact next greater --> stack

circular array 本身没有造成什么困扰，当作两个相同 array 首位相接就是了。

class Solution:
    def nextGreaterElements(self, nums: List[int]) -> List[int]:
        res = [-1 for _ in range(len(nums))]
        stack = collections.deque([])
        for _ in range(2):
            for i in range(len(nums)-1, -1, -1):
                if res[i] == -1:
                    while stack and nums[stack[-1]] <= nums[i]: stack.pop()
                    if stack: res[i] = nums[stack[-1]]
                stack.append(i)
        return res