每日一题：LeetCode-739. 每日温度

2024-01-24
北京
本文字数：894 字
阅读完需：约 3 分钟

刷题使我快乐，满脸开心.jpg

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/daily-temperatures/
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题目

给定一个整数数组 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

思路

这个题目直接暴力肯定是没有问题，那么最大的问题就在于如何优化了

单调栈

之前也分享过几个单调栈的题目，有必要可以顺着标签过去看看哈~

熟悉这种思路的话，应该能够很快想到单调栈

单调栈本身也确实很适合应对这种找下一个更大、更小元素的问题：

一个个元素遍历
栈内元素比当天温度低的，弹出，并且也就可以记录结果了
直到遇到比当天温度高的或者栈空了，那就直接入栈，等待后续天的数据

基本代码思路就是这样啦，直接上代码，细节在注释了

代码

func dailyTemperatures(temperatures []int) []int {    // 存储下标的栈    stack := make([]int, 0, len(temperatures))    ans := make([]int, len(temperatures))        for i := range temperatures {        // 不为空则尝试比对        for len(stack) > 0 {            // 如果栈顶位置的下标对应温度低于当前温度，那就可以出栈并记录结果            if temperatures[stack[len(stack)-1]] < temperatures[i] {                ans[stack[len(stack)-1]] = i - stack[len(stack)-1]                stack = stack[:len(stack)-1]            } else {                break            }        }        // 当前温度的下标入栈        stack = append(stack, i)    }    // ans中没有写入结果的也就是最终没有找到更高温度的    // 跟初始化值0相同，所以不用特殊处理了    return ans}

复制代码

欢迎关注公众号交流更多题目~

发布于: 19 分钟前阅读数: 5

原文链接:【http://xie.infoq.cn/article/8f0cefcc828fb4f97d00310aa】。文章转载请联系作者。

半亩房顶

关注

人生那么长，能写多少bug？ 2018-11-16 加入

我希望，自己永远是自己。我希望，远离bug。

发布

暂无评论

创作场景

每日一题：LeetCode-739. 每日温度

题目

思路

单调栈

代码

半亩房顶

评论