leetcode739 每日温度

题目

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

示例

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

解析

这道题的测试用例其实可以用这个：

temp := []int{1, 4, 3, 5, 5, 2, 3, 6}

这道题可以有两种方法，首先看从左到右的方法：

func dailyFromLeft(temperature []int) []int {n := len(temperature)// 两个额外数组，一个存结果ans，这个默认已经初始化为0了，后面更新哪个位置，就将对应的下标间隔更新进去ans := make([]int, n)// 另一个就是栈，栈中存的是下标stack := []int{}for i, value := range temperature {for len(stack) > 0 && value > temperature[stack[len(stack)-1]] {j := stack[len(stack)-1]     // 之前存在栈里的下标stack = stack[:len(stack)-1] // 弹出栈顶ans[j] = i - j}stack = append(stack, i)}return ans
}

这道题愣是去理解的话，还是有点费劲，建议根据上面的那个测试用例来进行debug，首先在从左到右的顺序遍历过程中，栈中存的下标用j来表示，就相当于遍历到i的时候（此时j小i大，那距离就是i-j），就相当于在第一次遍历到的某个位置的时候，此时还不知道后面谁比他大的，遍历到第一个比它大的时候才进行计算，添加到ans中。

然后是从右到左的方法：

func dailyTemperatures(temperatures []int) []int {n := len(temperature)// 两个额外数组，一个存结果ans，这个默认已经初始化为0了，后面更新哪个位置，就将对应的下标间隔更新进去ans := make([]int, n)// 另一个就是栈，栈中存的是下标stack := []int{}for i := n - 1; i >= 0; i-- {value := temperature[i]for len(stack) > 0 && value >= temperature[stack[len(stack)-1]] { // 从右到左遍历，当前的高度大于栈中的数据，就弹出栈中的小的数据stack = stack[:len(stack)-1]}if len(stack) > 0 {ans[i] = stack[len(stack)-1] - i // 将栈中存的比当前位置大的下标与当前位置下标相减}stack = append(stack, i) // stack中存的是下标}return ans
}