每日温度

1. 题目描述

请根据每日 气温 列表，重新生成一个列表。对应位置的输出为：要想观测到更高的气温，至少需要等待的天数。如果气温在这之后都不会升高，请在该位置用 0 来代替。

例如，给定一个列表 temperatures = [73, 74, 75, 71, 69, 72, 76, 73]，你的输出应该是 [1, 1, 4, 2, 1, 1, 0, 0]。

2. 思路

1. 思路一
   • 暴力
   • 两层for循环找出后面第一个比当前值大的值

3. 实现

3.1. 暴力

package main

func dailyTemperatures(T []int) []int {
	res := make([]int, 0)

	for i := 0; i < len(T); i++ {
		minJ := i
		for j := i + 1; j < len(T); j++ {
			if T[j] > T[i] {
				minJ = j
				break
			}
		}
		res = append(res, minJ-i)
	}

	return res
}

3.2. 单调栈

func dailyTemperatures(temperatures []int) []int {
    res := make([]int, len(temperatures))
    var stack []int// 单调栈，存放递减的数的下标
    for i, num := range temperatures {
        //维护单调栈的性质同时输出结果
        for !empty(stack) && num > temperatures[top(stack)] {
            prevIndex := top(stack)
            stack = pop(stack)
            res[prevIndex] = i-prevIndex
        }
        stack = push(stack, i)
    
    }
    return res
}

func empty(stack []int) bool {
    return len(stack) == 0
}

func push(stack []int, i int) []int {
    stack = append(stack, i)
    return stack
}

func top(stack []int) int {
    return stack[len(stack)-1]
}

func pop(stack []int) []int {
    return stack[:len(stack)-1]
}

4. 参考

• 每日温度 - 每日温度 - 力扣（LeetCode）
• LeetCode 图解 | 739.每日温度 - 每日温度 - 力扣（LeetCode）