【代码随想录算法训练营第五十三天|739.每日温度、496.下一个更大元素I、503.下一个更大元素II】

739.每日温度

在这里单调栈相当于是在遍历数组的同时记录下了额外的大小关系的信息。因为这里需要的是每个数组元素右边第一个比他大的元素的间隔，因此单调栈是用来在遍历数组的时候存放还没有找到比他大的元素的下标，如果当前的元素比栈顶的元素大，那么就在结果对应的下标的位置记录下这个间隔，并且把该栈顶元素出栈，否则就入栈，等待后续的第一个比他大的元素出现。

class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        stack = [0]
        ans = [0] * len(temperatures)
        for i in range(1, len(temperatures)):
            if temperatures[i] <= temperatures[stack[-1]]:
                stack.append(i)
                continue
            while stack and temperatures[i] > temperatures[stack[-1]]:
                tmp = stack.pop()
                ans[tmp] = i - tmp
            stack.append(i)
        return ans
1
2
3
4
5
6
7
8
9
10
11
12
13

496.下一个更大元素I

本质上还是在nums2中找每个元素右边的第一个最大值，只是不是针对其中的所有元素而是部分子集，而且nums1和nums2中元素都不会重复。因此可以把nums1做成nums1[i]与i的字典键值对，然后对nums2用单调栈的方法去遍历找到每个元素下一个最大值，如果栈顶的元素在nums1中的话就在ans的对应位置出赋上这个数。

class Solution:
    def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
        ans = [-1] * len(nums1)
        temp1 = dict()
        for i in range(len(nums1)):
            temp1[nums1[i]] = i
        st = [0]
        for i in range(1, len(nums2)):
            while st and nums2[i] > nums2[st[-1]]:
                num = nums2[st.pop()]
                if num in temp1:
                    ans[temp1[num]] = nums2[i]
            st.append(i)
        return ans 
1
2
3
4
5
6
7
8
9
10
11
12
13
14

503.下一个更大元素II

先和上面一样正常的向右找最近的更大元素，然后全部遍历完之后，再根据还在单调栈中（这些就是在右边没有找到下一个更大元素的元素）的最大索引，也就是栈顶的元素在nums中再从左往右和栈顶的索引对应元素对比一次大小。

class Solution:
    def nextGreaterElements(self, nums: List[int]) -> List[int]:
        ans = [-1] * len(nums)
        st = [0]
        for i in range(1, len(nums)):
                while st and nums[i] > nums[st[-1]]:
                    temp = st.pop()
                    ans[temp] = nums[i]
                st.append(i)
        for i in range(st[-1]):
            while st and nums[i] > nums[st[-1]]:
                temp = st.pop()
                ans[temp] = nums[i]
        return ans
1
2
3
4
5
6
7
8
9
10
11
12
13
14