leetcode 每日温度 单调栈

739. 每日温度 - 力扣(LeetCode)


栈里边存放的是还没有找到后边更大值的元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
func dailyTemperatures(temperatures []int) []int {
n := len(temperatures)
ans := make([]int, n)
st := []int{}
for i, t := range temperatures {
for len(st) > 0 && t > temperatures[st[len(st)-1]] {
j := st[len(st)-1]
st = st[:len(st)-1]
ans[j] = i - j
}
st = append(st, i)
}
return ans
}

这段代码是一个Go语言编写的函数,名为dailyTemperatures,它使用单调栈的数据结构来解决一个特定问题:给定一个每日温度列表temperatures,返回一个新列表,其中第i个元素是温度列表中第i天之后第一个比第i天温度更高的温度的天数。

代码思想解释:

  1. 问题定义:我们想要找到一个序列中每个元素之后的第一个更大元素,并记录它们之间的索引差。

  2. 单调栈的应用:单调栈是一种特殊的栈结构,它保证栈内的元素是单调递增或单调递减的。在这个场景中,我们使用单调栈来维护一个索引栈,栈内元素代表尚未找到更大温度的天的索引。

  3. 初始化

    • n:记录输入温度数组的长度。
    • ans:初始化一个长度为n的数组,用于存储结果,初始值设为0。
    • st:初始化一个空的切片,用作单调栈。
  4. 遍历温度数组

    • 通过range关键字遍历temperatures数组,同时获取索引i和对应的温度值t
  5. 维护单调栈

    • 当前温度t大于栈顶元素对应的温度时,说明栈顶元素之后的第一个更高温度就是当前温度。此时,执行以下操作:
      • 弹出栈顶元素j,即st[len(st)-1]
      • 计算索引差i - j,并将这个差值赋给ans[j]
      • 更新栈st,移除栈顶元素。
  6. 压栈操作

    • 将当前索引i压入栈st中。这表示当前索引的天还没有找到之后的第一个更高温度。
  7. 返回结果

    • 遍历结束后,返回ans数组,其中每个元素表示对应天之后第一个更高温度的天数。

leetcode 每日温度 单调栈
https://leiqi.top/2024-05-20-1fbf9ee2486f.html
作者
Lei Qi
发布于
2024年5月21日
许可协议