代码随想录算法训练营第六十天 | 单调栈 part 1 | 739. 每日温度、496.下一个更大元素 I

739. 每日温度

Leetcode

思路

维持一个单调递增的栈，向栈逐一pushtemperatures里的index。

• 如果当前遍历的元素大于栈顶元素，这意味着 栈顶元素的 右边的最大的元素就是 当前遍历的元素，所以弹出 栈顶元素，并记录
• 否则的话，可以直接入栈。

代码

class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        stack = [0]
        answer = [0] * len(temperatures)

        for i in range(1, len(temperatures)):
            if temperatures[i] <= temperatures[stack[-1]]:
                stack.append(i)
            
            else:
                while len(stack) != 0 and temperatures[i] > temperatures[stack[-1]]:
                    answer[stack[-1]] = i - stack[-1]
                    stack.pop()
                stack.append(i)
        
        return answer
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

• 时间复杂度：O(n)
• 空间复杂度：O(n)

496.下一个更大元素 I

Leetcode

思路

这道题和上一题类似。

维护一个nums2的单调递增栈，只不过在pop的时候需要在nums1中寻找相应的index，这一步可以用.index()，也可以使用哈希表。

代码

.index()

class Solution:
    def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
        res = [-1] * len(nums1)
        stack = [0]

        for i in range(len(nums2)):
            if nums2[i] <= nums2[stack[-1]]:
                stack.append(i)
            else:
                while stack and nums2[i] > nums2[stack[-1]]:
                    if nums2[stack[-1]] in nums1:
                        index = nums1.index(nums2[stack[-1]])
                        res[index] = nums2[i]
                    stack.pop()
                stack.append(i)
        
        return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

哈希表

class Solution:
    def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
        res = [-1] * len(nums1)
        stack = [0]
        dic = {}
        for i, v in enumerate(nums1):
            dic[v] = i
        for i in range(len(nums2)):
            if nums2[i] <= nums2[stack[-1]]:
                stack.append(i)
            else:
                while stack and nums2[i] > nums2[stack[-1]]:
                    if nums2[stack[-1]] in nums1:
                        index = dic[nums2[stack[-1]]]
                        res[index] = nums2[i]
                    stack.pop()
                stack.append(i)
        
        return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19