栈的应用:每日温度

题目描述:

根据每日 气温 列表,请重新生成一个列表,对应位置的输入是你需要再等待多久温度才会升高超过该日的天数。如果之后都不会升高,请在该位置用 0 来代替。

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

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

题目解析:

对于输入 73,它需要 经过一天 才能等到温度的升高,也就是在第二天的时候,温度升高到 74 ,所以对应的结果是 1。

对于输入 74,它需要 经过一天 才能等到温度的升高,也就是在第三天的时候,温度升高到 75 ,所以对应的结果是 1。

对于输入 75,它经过 1 天后发现温度是 71,没有超过它,继续等,一直 等了四天,在第七天才等到温度的升高,温度升高到 76 ,所以对应的结果是 4 。

对于输入 71,它经过 1 天后发现温度是 69,没有超过它,继续等,一直 等了两天,在第六天才等到温度的升高,温度升高到 72 ,所以对应的结果是 2 。

对于输入 69,它 经过一天 后发现温度是 72,已经超过它,所以对应的结果是 1 。

对于输入 72,它 经过一天 后发现温度是 76,已经超过它,所以对应的结果是 1 。

对于输入 76,后续 没有温度 可以超过它,所以对应的结果是 0 。

对于输入 73,后续 没有温度 可以超过它,所以对应的结果是 0 。

具体代码如下:

t = [73, 74, 75, 71, 69, 72, 76, 73]

def daily_temp(tem):
    # 模拟一个递减栈,存放当天的索引
    stack = []
    # 结果列表,几天后气温才升高
    res = [0] * len(tem)
    # 循环整个列表
    for i in range(len(tem)):
        # 当栈不为空且当前天数的气温大于栈顶的气温时,计算栈顶那天过几天气温才会升高
        while stack and tem[i] > tem[stack[-1]]:
            res[stack[-1]] = i - stack[-1]
            # 计算完出栈
            stack.pop()
        # 栈为空或者没有超过的温度,入栈一个
        stack.append(i)

    return res

if __name__ == '__main__':
    print(daily_temp(t))

原文地址:https://www.cnblogs.com/milesma/p/12461949.html