单调栈模型-JZTXT

单调栈本质: 及时去掉无用数据, 保证栈中数据有序。

模板题:

class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        n = len(temperatures)
        stk = []
        ans = [0] * n
        for i in range(n - 1, -1, -1):
            t = temperatures[i]
            while stk and t >= temperatures[stk[-1]]:
                stk.pop()
            if stk:
                ans[i] = stk[-1] - i
            stk.append(i)
        
        return ans

class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        n = len(temperatures)
        stk = []
        ans = [0] * n
        for i, t in enumerate(temperatures):
            while stk and temperatures[stk[-1]] < t:
                j = stk.pop()
                ans[j] = i - j
            stk.append(i)
        
        return ans

数组的循环操作可以用模运算来实现

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

        for i in range(n * 2):
            while stk and nums[stk[-1]] < nums[i % n]:
                j = stk.pop()
                ans[j] = nums[i % n]
            stk.append(i % n)
        
        return ans

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

        for i in range(n * 2 - 1, -1, -1):
            while stk and nums[stk[-1]] <= nums[i % n]:
                stk.pop()
            if stk:
                ans[i % n] = nums[stk[-1]]
            stk.append(i % n)
        
        return ans