每日温度

Leetcode Link: 739. 每日温度 - 力扣（LeetCode）

题目

给定一个整数数组 temperatures ，表示每天的温度，返回一个数组 answer ，其中 answer[i] 是指对于第 i 天，下一个更高温度出现在几天后。如果气温在这之后都不会升高，请在该位置用 0 来代替。

解法一

思路： 就是单调栈的用法

需要注意的情况已经标注了，这是我自己盲写的，没看过正规的单调栈代码，这里应该还能进一步优化。

Note

• 这是有重复的单调栈，因此需要存入的是列表
• 下面的两块区域是固定的，1，2 顺序变动会报错，没有 3 处理最后剩下的不行
• 这个单调栈是小的在上，大的在下。

题解：

class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        stack = collections.deque()
        ans = [0]* len(temperatures)
        for i in range(len(temperatures)):
	        # - 1 处理大值
            while(stack and (temperatures[i] > temperatures[stack[-1][-1]])):
                cur = stack.pop()
                for j in cur:
                    ans[j] = i - j
			# - 2 处理当前值（在1中，大值没有被处理）
            if stack and (temperatures[i] == temperatures[stack[-1][-1]]):
                stack[-1].append(i)
            elif stack and (temperatures[i] < temperatures[stack[-1][-1]]):
                stack.append([i])
            elif not stack:
                stack.append([i])
                
        # 处理栈里剩下的
        while(stack):
            cur = stack.pop()
            for j in cur:
                ans[j] = 0
        return ans
 

网友的简化版

class Solution(object):
    def dailyTemperatures(self, temperatures):
        stack = collections.deque()
        t_length = len(temperatures)
        res_list = [0] * t_length
        
        for key, value in enumerate(temperatures):     
            while stack and temperatures[stack[-1]] < value:
                res_list[stack[-1]] = key - stack[-1]
                stack.pop()
            # 相等的不需要列表也行，因为不用考虑当前位置之前更小的元素
            stack.append(key)
 
			# 初始化时已经是0了，所以不需要处理栈里剩下的。
 
        return res_list

解法二

思路 暴力，两个for可以处理

启发和联系