739. 每日温度

题目描述

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

示例 1:

1
2


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

示例 2:

1
2


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

示例 3:

1
2


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

提示：

1 <= temperatures.length <= 10⁵
30 <= temperatures[i] <= 100

解法一：单调栈

下面代码使用单调递减栈（从栈底到栈顶单调递减）来解决这个问题

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


func dailyTemperatures(temperatures []int) []int {
    res := make([]int, len(temperatures))
    var descStack []int
    for i := 0; i < len(temperatures); i++ {
        for len(descStack) > 0 && temperatures[i] > temperatures[descStack[len(descStack)-1]] {
            res[descStack[len(descStack)-1]] = i - descStack[len(descStack)-1]
            descStack = descStack[:len(descStack)-1]
        }
        descStack = append(descStack, i)
    }
    for len(descStack) > 0 {
        res[descStack[len(descStack)-1]] = 0
        descStack = descStack[:len(descStack)-1]
    }
    return res
}