【LeetCode 刷题】单调栈(1)-下一更大元素

此博客为《代码随想录》单调栈章节的学习笔记，主要内容为单调栈下一更大元素问题的相关题目解析。

文章目录

• 739. 每日温度
• 496.下一个更大元素 I
• 503.下一个更大元素II

739. 每日温度

题目链接

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

• 栈中记录还没算出下一个更大元素的那些数的下标
• 当前元素 <= 栈顶元素时，才入栈；否则弹出栈中不满足条件的元素，记录答案

496.下一个更大元素 I

题目链接

class Solution:
    def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
        idx = {x: i for i, x in enumerate(nums1)}
        res = [-1] * len(nums1)
        stk = []
        for x in nums2:
            while stk and x > stk[-1]:
                pre = stk.pop()
                res[idx[pre]] = x
            if x in idx:
                stk.append(x)
        return res

• 提前建立 nums1 的索引字典，后续单调栈中便可直接压入元素值，而非元素下标
• 遍历 nums2 获取下一个更大元素信息，但只把那些同时在 nums1 中的元素压入栈，不在 nums1 中的元素不需要实际求解其下一个更大元素

503.下一个更大元素II

题目链接

class Solution:
    def nextGreaterElements(self, nums: List[int]) -> List[int]:
        n = len(nums)
        res = [-1] * n
        stk = []
        for i in range(n + n):
            while stk and nums[i%n] > nums[stk[-1]]:
                res[stk.pop()] = nums[i%n]
            if i < n:
                stk.append(i)
        return res

• 循环数组，处理方式为后面再拼接一遍数组，通过下标取余方式避免实际的数组拼接
• 只有在第一段数组的元素才需要被加入栈，第二段数组的元素不应加入栈，否则会重新计算已经计算好的元素