代码随想录算法训练营day62 | 739. 每日温度、496.下一个更大元素 I 、503.下一个更大元素II

单调栈

通常是一维数组，要寻找任一个元素的右边或者左边第一个比自己大或者小的元素的位置，此时我们就要想到可以用单调栈了。时间复杂度为O(n)。

单调栈的本质是空间换时间，因为在遍历的过程中需要用一个栈来记录右边第一个比当前元素高的元素，优点是整个数组只需要遍历一次。

使用单调栈主要有三个判断条件。

• 当前遍历的元素T[i]小于栈顶元素T[st.top()]的情况
• 当前遍历的元素T[i]等于栈顶元素T[st.top()]的情况
• 当前遍历的元素T[i]大于栈顶元素T[st.top()]的情况

739. 每日温度

栈里面存储索引，可以通过索引获取数值。当前值遇到大于栈顶元素的，则弹出栈中元素，直至栈顶元素大于等于当前值。

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

496.下一个更大元素 I

求的是nums1中的元素在nums2数组中右侧第一个大的元素。因此最后返回的是和nums1一样大小的数组。使用单调栈的方式遍历nums2，遇到写结果的时候使用nums1的索引写入结果集。

class Solution:
    def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
        result = [-1] * len(nums1)
        hash_map = dict()
        for i, num in enumerate(nums1):
            hash_map[num] = i
        stack = []
        for i in range(len(nums2)):
            while stack and nums2[i] > nums2[stack[-1]]:
                if nums2[stack[-1]] in hash_map:
                    result[hash_map[nums2[stack[-1]]]] = nums2[i]
                stack.pop()
            stack.append(i)
        return result

503.下一个更大元素II

循环数组重复一遍即可，可以使用取余的方式优化代码

class Solution:
    def nextGreaterElements(self, nums: List[int]) -> List[int]:
        result = [-1] * len(nums)
        stack = []
        for i in range(len(nums)):
            while stack and nums[i] > nums[stack[-1]]:
                result[stack[-1]] = nums[i]
                stack.pop()
            stack.append(i)
        for i in range(len(nums)):
            while stack and nums[i] > nums[stack[-1]]:
                result[stack[-1]] = nums[i]
                stack.pop()
            stack.append(i)
        return result