LeetCode-739. 每日温度 - sheep44044的小站

栈#

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

示例 1:

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

示例 2:

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

示例 3:

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

思路

尝试写一下逻辑为什么用单调栈

这题暴力法两个for要重复扫描，所以需要数据结构存储数据
求最近的较大值，所以需要栈
大的会挡住小的，小的没用了，所以栈必须是单调的。

所以，这题可以得出需要单调栈

1
func dailyTemperatures(temperatures []int) []int {
2
    n := len(temperatures)
3
    res := make([]int, n)
4
    stack := make([]int, 0)
5

6
    for i, v := range temperatures {
7
        for len(stack) > 0 && v > temperatures[stack[len(stack)-1]] {
8
            index := stack[len(stack)-1]
9
            stack = stack[:len(stack)-1]
10
            res[index] = i - index
11
        }
12
        stack = append(stack, i)
13
    }
14
    return res
15
}