LeetCode - 739.Daily Temperatures

题目描述

原题链接

Given an array of integers temperatures represents the daily temperatures, return an array answer such that answer[i] is the number of days you have to wait after the i^th day to get a warmer temperature. If there is no future day for which this is possible, keep answer[i] == 0 instead.

Example 1:

1
2

Input: temperatures = [73,74,75,71,69,72,76,73]
Output: [1,1,4,2,1,1,0,0]

Example 2:

1
2

Input: temperatures = [30,40,50,60]
Output: [1,1,1,0]

Example 3:

1
2

Input: temperatures = [30,60,90]
Output: [1,1,0]

Constraints:

• 1 <= temperatures.length <= 10^5
• 30 <= temperatures[i] <= 100

解题方法

单调栈

题目的意思实际上就是给定一个数组，每个位置上有整数值。对于每个位置，在该位置右侧找到第一个比当前元素更大的元素。求「该元素」与「右侧第一个比当前元素更大的元素」之间的距离，将所有距离保存为数组返回结果。

最简单的思路是对于每个温度值，向后依次进行搜索，找到比当前温度更高的值。

更好的方式使用「单调递增栈」，栈中保存元素的下标。

解题思路：

1. 将答案数组 ans 全部赋值为 0，然后遍历数组每个位置元素。
2. 如果栈为空，则将当前元素的下标入栈。
3. 如果栈不为空，且当前数字大于栈顶元素对应的数字，栈顶元素出栈，计算下标差。
4. 此时当前元素就是栈顶元素的下一个更高值，将其下标差存入 ans 数组中保存起来，判断栈顶元素。
5. 直到当前数字小于或等于栈顶元素，则停止出栈，将当前元素下标入栈。
6. 输出数组 ans

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        n = len(temperatures)
        # 初始化答案数组
        ans = [0] * n
        # 单调递增栈
        st = []
        # 遍历
        for i, temp in enumerate(temperatures):
            # 当前温度大于栈顶，出栈，计算下标差存入答案数组
            while st and temperatures[st[-1]] < temp:
                idx = st.pop()
                ans[idx] = i - idx
            # 当前温度小于栈顶元素，入栈
            st.append(i)
        return ans

时间复杂度：$O(n)$

空间复杂度：$O(n)$