739 每日温度

标签: 栈

题目

题目链接：739 每日温度

请根据每日 气温 列表，重新生成一个列表。对应位置的输出为：要想观测到更高的气温，至少需要等待的天数。如果气温在这之后都不会升高，请在该位置用 0 来代替。

例如，给定一个列表 temperatures = [73, 74, 75, 71, 69, 72, 76, 73]，你的输出应该是 [1, 1, 4, 2, 1, 1, 0, 0]。

提示：气温 列表长度的范围是 [1, 30000]。每个气温的值的均为华氏度，都是在 [30, 100] 范围内的整数。

思路

1. 使用栈来暂存：截至目前为止温度下降的趋势，遇到温度大于栈顶元素的，需要弹出栈顶。入栈出栈顺序见下表：

   输入：[73, 74, 75, 71, 69, 72, 76, 73]

   curr	stack	res	comment
   73	[(0, 73)]	[0, 0, 0, 0, 0, 0, 0, 0]	压入第一个元素的 (索引，元素)
   74	[(1, 74)]	[1, 0, 0, 0, 0, 0, 0, 0]	curr(74) > 栈顶(73)，需要将 73 弹出栈 ，在 res 中 73 的位置存入 74 和 73 的索引差
   75	[(2, 75)]	[1, 1, 0, 0, 0, 0, 0, 0]	同上
   71	[(2, 75), (3, 71)]	[1, 1, 0, 0, 0, 0, 0, 0]	curr(71) < 栈顶(75)，直接入栈 71
   69	[(2, 75), (3, 71), (4, 69)]	[1, 1, 0, 0, 0, 0, 0, 0]	同上，入栈 69
   72	[(2, 75), (5, 72)]	[1, 1, 0, 2, 1, 0, 0, 0]	curr(72) > 栈顶(69)，将 69 弹出栈，在 res 中保存索引差。此时，栈顶 71 依然小于 72，继续弹出栈。
   76	[(6, 76)]	[1, 1, 4, 2, 1, 1, 0, 0]	curr(76) 比栈内所有元素都大，所以栈内元素都要弹出，并在 res 中存入索引差
   73	[(6, 76), (7, 73)]	[1, 1, 4, 2, 1, 1, 0, 0]	curr(73) < 栈顶(76)，直接入栈 73

代码

class Solution:
    def dailyTemperatures(self, T: List[int]) -> List[int]:
        res = [0] * len(T)
        stack = []
        for index, item in enumerate(T):
            while stack and stack[-1][1] < item:
                idx, it = stack.pop()
                res[idx] = index - idx
            stack.append((index, item))
        return res

分析

时间复杂度和空间复杂度都需要 O(n)，只需要遍历一次即可。