算法 LeetCode 题解 | 每日温度

大家好，我是木川

一、题目描述

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

示例 1:

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

示例 2:

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

示例 3:

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

提示：

• 1 <= temperatures.length <= 105

• 30 <= temperatures[i] <= 100

二、题解

一）暴力算法

思路：先看下最简单的思路，暴力算法肯定很耗时，肯定不会通过，这里写出来只是了解下思路

1、 第一层循环遍历数组元素

2、第二层循环遍历当前元素后面的元素，如果碰到比当前元素大，则结束

代码：

func dailyTemperatures(temperatures []int) []int {
    res := make([]int, len(temperatures))
    for i := 0; i < len(temperatures); i++ {
        find := false
        for j := i+1; j < len(temperatures); j++ {
            res[i] ++
            if temperatures[j] > temperatures[i] {
                find = true
                break
            }
        }
        // 没找到比当前元素的大
        if !find {
            res[i] = 0
        }
    }
 
    return res
}

时间复杂度：O(n ^ 2)

空间复杂度：O(n)

二）单调栈栈

单调栈：栈中元素要么单调递减，要么单调递增，本题使用递减栈

思路：

1、遍历整个数组，如果栈不空，且当前数字大于栈顶元素则取出栈顶元素，由于当前数字大于栈顶元素的数字，而且一定是第一个大于栈顶元素的数，直接求出下标差就是二者的距离

2、继续看新的栈顶元素，直到当前数字小于等于栈顶元素停止，然后将数字入栈，这样就可以一直保持递减栈，且每个数字和第一个大于它的数的距离也可以算出来

代码：

func dailyTemperatures(temperatures []int) []int {
    res := make([]int, len(temperatures))
    stack := make([]int, 0)
    for i := 0; i < len(temperatures); i++ {
        // 当前元素 > 栈顶元素
        for (len(stack) > 0 && temperatures[i] > temperatures[stack[len(stack)-1]]) {
            // 栈顶元素对应的下标（之前访问的元素）
            // 当前下标 - 栈顶元素下标 = 第一个大于它的数的距离
            idx := stack[len(stack)-1]
            res[idx] = i - idx
            // 出栈操作：前一个元素下标出栈
            stack = stack[0:len(stack)-1]
        }
        // 入栈操作：压入当前遍历元素对应的下标
        stack = append(stack, i)
    }
 
    return res
}

时间复杂度：O(n)，n 为数组的长度，正向遍历数组一遍，对于每个元素，最多有一次进栈和出栈的操作

空间复杂度：O(n)

今天的分享就到这里了，加下面微信拉你进编程技术交流群

如果对你有帮助，帮我点一下在看或转发，欢迎关注我的公众号