题解 | #每日温度#

题目分析

1. 题目给出我们一个数组，表示每天的温度值
2. 题目要求我们返回一个数组，每个元素表示，对于该天的温度，再经过几天温度比该天温度高，将这个天数的差值作为该元素放到返回数组中。如果不存在更高的温度了，则用0填充

方法一：暴力遍历

• 实现思路

  • 我们外层循环遍历每一天

  • 内层循环遍历该天之后的所有天数

  • 判断该天之后是否有更高的温度出现，如果有，则添加下标差j-i到我们的res数组中，如果没有则添加0到res数组中

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 每日温度
# @param dailyTemperatures int整型一维数组 
# @return int整型一维数组
#
class Solution:
    def temperatures(self , dailyTemperatures: List[int]) -> List[int]:
        # write code here
        n = len(dailyTemperatures)
        res = []
        for i in range(n):
            cur = dailyTemperatures[i]        # 待比较的温度cur
            for j in range(i+1,n):
                nxt = dailyTemperatures[j]    # 查找cur之后是否存在比cur温度要高的nxt
                if nxt > cur:
                    res.append(j-i)
                    break
            if len(res) == i:
                res.append(0)
        return res

复杂度分析

• 时间复杂度：$O(n^2)O(n^2)$，双重循环引入的时间代价
• 空间复杂度：$O(n)O(n)$，结果数组的空间大小与输入数组的空间大小呈线性关系

方法二：单调栈

• 实现思路
  • 我们维护一个单调栈stack
  • 单调栈中我们只将比栈顶温度小的温度入栈（其实我们栈中所有元素都是温度的下标，但是理解起来表示的含义是温度）
  • 这样当有遍历到一个温度比栈顶高的时候，就可以将栈顶元素出栈，并计算天数之差，并循环这一个过程。直到栈中所有温度都已经出栈了，或者栈顶温度更高，此时将该天温度入栈
  • 对所有的遍历的温度都重复上一个过程，即能够将结果计算出来

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 每日温度
# @param dailyTemperatures int整型一维数组 
# @return int整型一维数组
#
class Solution:
    def temperatures(self , dailyTemperatures: List[int]) -> List[int]:
        # write code here
        n = len(dailyTemperatures)
        res = [0]*n
        stack = [-1]                    # 辅助元素，由于温度不会低于0，因此我们添加一个温度-1来方便比较
        
        for i in range(n):
            cur = dailyTemperatures[i]
            while cur > dailyTemperatures[stack[-1]] and len(stack) > 1:    # 如果当前天的温度 > 单调递减栈中最后一个位置的温度，则执行退栈操作
                res[stack[-1]] = i - stack[-1]
                stack.pop()
            stack.append(i)
        return res

复杂度分析

• 时间复杂度：$O(n)O(n)$，由于单调栈的存在，我们最坏的情况就是前$n-1n-1$天的温度递减，第n天的温度最高。这样的操作步数就是$n-1n-1$个元素进栈一次，并在遍历到第n个元素的时候全部出栈。共计时间代价仍然与元素个数呈线性关系
• 空间复杂度：$O(n)O(n)$，结果数组的空间大小与输入数组的空间大小呈线性关系