739每日温度.md

方法一：暴力

func dailyTemperatures(temperatures []int) []int {
    n := len(temperatures)
    for i := 0; i < n; i++ {
        found := false
        for j := i+1; j < n; j++ {
            if temperatures[j] > temperatures[i] {
                temperatures[i] = j - i
                found = true
                break
            }
        }
        if !found {
            temperatures[i] = 0
        }
    }
    return temperatures
}

方法二：较优化，从后往前遍历，同时用一个next数组保存所有温度值的最早出现下标

func dailyTemperatures(temperatures []int) []int {
    n := len(temperatures)
    next := make([]int, 101) // 从0到100度一共有101种可能的温度值
    for i := range next {
        next[i] = math.MaxInt32
    }
    for i := n-1; i >= 0; i-- {
        foundAt := math.MaxInt32
        for j := temperatures[i]+1; j <= 100; j++ { // 从比当前温度高1度开始遍历，查看next中有没有更小的index
            if next[j] < foundAt {
                foundAt = next[j]
            }
        }
        next[temperatures[i]] = i // 在next里更新当前温度出现的下标，因为是从后往前遍历，所以当前坐标一定是最小的
        if foundAt < math.MaxInt32 {
            temperatures[i] = foundAt - i
        } else {
            temperatures[i] = 0
        }
    }
    return temperatures
}

方法三：最优解，使用单调递减栈

func dailyTemperatures(temperatures []int) []int {
    n := len(temperatures)
    ans := make([]int, n)
    stack := []int{} // 单调栈
    for i := 0; i < n; i++ {
        temperature := temperatures[i]
        for len(stack) > 0 && temperature > temperatures[stack[len(stack)-1]] {
            prev := stack[len(stack)-1]
            ans[prev] = i - prev
            stack = stack[:len(stack)-1]
        }
        stack = append(stack, i)
    }
    return ans
}