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


      目录
      相关文章
      |
      2月前
      |
      C++
      leetcode739 每日温度
      leetcode739 每日温度
      |
      2月前
      |
      算法
      代码随想录算法训练营第五十七天 | LeetCode 739. 每日温度、496. 下一个更大元素 I
      代码随想录算法训练营第五十七天 | LeetCode 739. 每日温度、496. 下一个更大元素 I
      31 3
      |
      2月前
      |
      存储 算法
      代码随想录算法训练营第五十九天 | LeetCode 739. 每日温度、496. 下一个更大元素 I
      代码随想录算法训练营第五十九天 | LeetCode 739. 每日温度、496. 下一个更大元素 I
      30 1
      |
      2月前
      |
      索引
      leetcode代码记录(每日温度
      leetcode代码记录(每日温度
      21 0
      |
      2月前
      |
      容器
      代码随想录 Day49 单调栈01 LeetCode LeetCodeT739每日温度 T496 下一个最大元素I
      代码随想录 Day49 单调栈01 LeetCode LeetCodeT739每日温度 T496 下一个最大元素I
      47 0
      |
      2月前
      |
      SQL
      leetcode-SQL-197. 上升的温度
      leetcode-SQL-197. 上升的温度
      23 0
      |
      2月前
      |
      索引
      leetcode-739:每日温度
      leetcode-739:每日温度
      33 0
      【LeetCode-每日一题】-739-每日温度
      【LeetCode-每日一题】-739-每日温度
      |
      11月前
      力扣739 每日温度
      力扣739 每日温度
      50 0
      |
      测试技术 数据库
      LeetCode(数据库)- 上升的温度
      LeetCode(数据库)- 上升的温度
      123 0