一天一道算法题（29）：单调栈

739. 每日温度

文章目录

• • [739. 每日温度](https://leetcode.cn/problems/daily-temperatures/)
  • – 暴力
  • – 单调栈
  • • – 图文解析
  • 结语

给定一个整数数组 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]

思路

– 暴力

• 空间复杂度O(1)（在力扣里面使用原数组记录不算入空间复杂度），时间复杂度O(n)

• 嵌套循环，第一层遍历每一个元素，第二层循环遍历该元素后面的每一个元素，如果发现存在更大值，就break，把结果写入数组，这里我为了避免超时，使用了原数组直接修改值，最后返回原数组的方式，可惜还是超时了，没有办法，所以我们要使用时间复杂度更低的办法了

• func dailyTemperatures(temperatures []int) []int {
  for i := 0; i < len(temperatures); i++ {
  flag := 0
  var j int
  for j = i+1; j < len(temperatures); j++ {
  if temperatures[j] > temperatures[i] {
  flag = 1
  break
  }
  }
  if flag == 1 {
  temperatures[i] = j–i
  } else {
  temperatures[i] = 0
  }
  }
  return temperatures
  }

– 单调栈

• 我们维护一个单调递减栈，这个单调递减栈的操作是这样的

• 第一种情况是栈为空或者当前温度小于等于栈顶温度，这符合递减栈的规则，所以直接将当前下标入栈。

• 第二种情况是当前温度大于栈顶温度，这说明栈顶元素已经找到了它需要的更高温度，于是进入内层循环，只要栈不为空且当前温度继续大于栈顶温度，就反复计算天数差并写入数组，同时将栈顶弹出。内层循环结束后，当前温度也要作为新的栈顶元素入栈，以便后续比较。

• 当整个数组遍历完成后，栈中可能还会剩余一些下标，这些下标对应的日子再也没有遇到更高的温度，根据题目要求需要将它们对应的位置赋值为零。最后返回这个被修改过的数组，就是最终答案

– 图文解析

• func dailyTemperatures(temperatures []int) []int {
  //单调栈
  stack := []int{}
  for i, v := range temperatures {
  //当前元素大于栈顶元素的时候，弹出，直到符合单调栈的情况
  for len(stack) != 0 && v > temperatures[stack[len(stack)–1]] {
  temperatures[stack[len(stack)–1]] = i–stack[len(stack)–1]
  stack = stack[:len(stack)–1]
  }
  //对当前元素入栈
  stack = append(stack, i)
  }
  //剩余的元素也要出栈，对于剩余的元素把结果直接记录为0
  for _, v := range stack {
  temperatures[v] = 0
  stack = stack[:len(stack)–1]
  }
  return temperatures
  }

结语

本文是 《算法题目解析系列》 的第 [29] 篇，本系列将持续更新，每篇都提供清晰的思路与编程语言实现。欢迎关注，第一时间获取更新。如果你有想看的题目，也可以在评论区留言告诉我。