LeetCode 739. 每日温度

简介: LeetCode 739. 每日温度

 739. 每日温度

   

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

示例 1:

输入: temperatures = [73,74,75,71,69,72,76,73]
输出: [1,1,4,2,1,1,0,0]

示例 2:

输入: temperatures = [30,40,50,60]
输出: [1,1,1,0]

示例 3:

输入: temperatures = [30,60,90]
输出: [1,1,0]

提示:

    • 1 <= temperatures.length <= 105
    • 30 <= temperatures[i] <= 100


    思路

    参考 LeetCode视频题解 - 单调栈

    注意题目要求的是升温的天数,而不是升温后的温度,因此栈中应存储下标,而非温度

      • 若当日温度 temperature 大于 "栈顶代表的第i天所对应温度temperatures[stack[len(stack)-1]] ",则将栈顶元素出栈,并计算其与当日相差的天数即可
      • 若栈为空 或 当前温度 temperature 小于等于 "栈顶代表的第i天所对应温度temperatures[stack[len(stack)-1]] ",则将当前温度的下标 index 直接入栈


      时间复杂度

      O(n),其中 n 是温度列表的长度。正向遍历温度列表一遍,对于温度列表中的每个下标,最多有一次进栈出栈的操作。


      空间复杂度

      O(n),其中 n 是温度列表的长度。需要维护一个单调栈存储温度列表中的下标。

      // 参考官方视频题解 单调栈:注意题目要求的是升温的天数,而不是升温后的温度,因此栈中应存储下标,而非温度funcdailyTemperatures(temperatures []int) []int {
      stack, res :=make([]int, 0), make([]int, len(temperatures))
      fori, temperature :=rangetemperatures {
      // 若当日温度temperature大于 "栈顶代表的第i天所对应温度temperatures[stack[len(stack)-1]]",则将栈顶元素出栈,并计算其与当日相差的天数即可// 至于内部用for循环,是因为当前温度temperature可能大于之前已入栈的多个温度,需逐个处理forlen(stack) >0&&temperature>temperatures[stack[len(stack)-1]] {
      res[stack[len(stack)-1]] =i-stack[len(stack)-1]
      stack=stack[:len(stack)-1] // pop        }
      // 若栈为空 或 当前温度temperature小于等于 "栈顶代表的第i天所对应温度temperatures[stack[len(stack)-1]]",则将当前温度的下标index直接入栈stack=append(stack, i)
          }
      returnres}
      // 暴力法:超时// func dailyTemperatures(temperatures []int) []int {//     l := len(temperatures)//     res := make([]int, l)//     for i := 0; i < l - 1; i++ {//         for j := i + 1; j < l; j++ {//             if temperatures[j] > temperatures[i] {//                 res[i] = j - i//                 break//             }//         }//     }//     return res// }

      image.gif


      目录
      相关文章
      |
      4月前
      |
      Go 索引
      【LeetCode 热题100】739:每日温度(详细解析)(Go语言版)
      这篇文章详细解析了 LeetCode 第 739 题“每日温度”,探讨了如何通过单调栈高效解决问题。题目要求根据每日温度数组,计算出等待更高温度的天数。文中推荐使用单调递减栈,时间复杂度为 O(n),优于暴力解法的 O(n²)。通过实例模拟和代码实现(如 Go 语言版本),清晰展示了栈的操作逻辑。此外,还提供了思维拓展及相关题目推荐,帮助深入理解单调栈的应用场景。
      149 6
      |
      存储 Python
      【Leetcode刷题Python】739. 每日温度
      LeetCode题目“739. 每日温度”的Python解决方案,使用单调栈来高效地计算出每天需要等待多少天才能遇到更暖天气的答案。
      157 4
      |
      算法
      代码随想录算法训练营第五十七天 | LeetCode 739. 每日温度、496. 下一个更大元素 I
      代码随想录算法训练营第五十七天 | LeetCode 739. 每日温度、496. 下一个更大元素 I
      94 3
      |
      存储 算法
      代码随想录算法训练营第五十九天 | LeetCode 739. 每日温度、496. 下一个更大元素 I
      代码随想录算法训练营第五十九天 | LeetCode 739. 每日温度、496. 下一个更大元素 I
      66 1
      |
      索引
      leetcode代码记录(每日温度
      leetcode代码记录(每日温度
      99 0
      |
      测试技术 数据库
      LeetCode(数据库)- 上升的温度
      LeetCode(数据库)- 上升的温度
      178 0
      |
      容器
      代码随想录 Day49 单调栈01 LeetCode LeetCodeT739每日温度 T496 下一个最大元素I
      代码随想录 Day49 单调栈01 LeetCode LeetCodeT739每日温度 T496 下一个最大元素I
      114 0
      |
      SQL
      leetcode-SQL-197. 上升的温度
      leetcode-SQL-197. 上升的温度
      86 0
      |
      索引
      leetcode-739:每日温度
      leetcode-739:每日温度
      97 0

      热门文章

      最新文章