当前位置: 首页 > news >正文

LeetCode 热题 100 739. 每日温度

LeetCode 热题 100 | 739. 每日温度

大家好,今天我们来解决一道经典的算法题——每日温度。这道题在 LeetCode 上被标记为中等难度,要求我们找到一个数组,其中每个元素表示从当前天开始,下一个更高温度出现的天数。如果之后没有更高的温度,则用 0 代替。下面我将详细讲解解题思路,并附上 Python 代码实现。


问题描述

给定一个整数数组 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. 单调栈

    • 使用一个栈来存储温度的索引,栈内元素保持单调递减的顺序。
    • 遍历温度数组时,如果当前温度大于栈顶温度,说明找到了一个更高的温度,可以更新答案并弹出栈顶元素。
    • 如果当前温度小于或等于栈顶温度,直接将当前索引入栈。
  2. 答案数组初始化

    • 初始化答案数组 answer,长度与 temperatures 相同,所有元素初始值为 0。如果后续没有找到更高的温度,这些位置的值将保持为 0

Python代码实现

def dailyTemperatures(temperatures):n = len(temperatures)answer = [0] * n  # 初始化答案数组stack = []  # 单调栈,存储温度的索引for i, temp in enumerate(temperatures):# 当前温度大于栈顶温度,更新答案并弹出栈顶元素while stack and temp > temperatures[stack[-1]]:prev_index = stack.pop()answer[prev_index] = i - prev_index# 当前索引入栈stack.append(i)return answer# 测试示例
print(dailyTemperatures([73,74,75,71,69,72,76,73]))  # 输出: [1,1,4,2,1,1,0,0]
print(dailyTemperatures([30,40,50,60]))  # 输出: [1,1,1,0]
print(dailyTemperatures([30,60,90]))  # 输出: [1,1,0]

代码解析

  1. 初始化答案数组和栈

    • answer 初始化为长度为 n 的数组,所有元素为 0
    • stack 用于存储温度的索引,保持单调递减的顺序。
  2. 遍历温度数组

    • 使用 enumerate 遍历温度数组,同时获取索引和温度值。
  3. 更新答案并弹出栈顶元素

    • 如果当前温度大于栈顶温度,说明找到了一个更高的温度,计算天数差并更新答案数组,然后弹出栈顶元素。
    • 重复上述步骤,直到栈为空或当前温度小于等于栈顶温度。
  4. 当前索引入栈

    • 将当前索引入栈,继续遍历。
  5. 返回答案数组

    • 最终返回答案数组 answer

复杂度分析

  • 时间复杂度:O(n),其中 n 是数组的长度。每个元素最多入栈和出栈一次。
  • 空间复杂度:O(n),栈的大小最多为 n

示例运行

示例 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]

总结

通过使用单调栈,我们可以高效地找到每个温度之后的第一个更高温度。这种方法不仅简洁,而且效率非常高,适合处理类似的问题。希望这篇题解对大家有所帮助,如果有任何问题,欢迎在评论区留言讨论!

关注我,获取更多算法题解和编程技巧!

http://www.lqws.cn/news/141535.html

相关文章:

  • 修复与升级suse linux
  • Viggle:开启视频人物替换新纪元
  • 滑动智能降级:Glide优化加载性能的黑科技
  • 用布局管理器grid实现计算机界面
  • Win11系统输入时首字母丢失 - 解决方案
  • 11. 试学内容-如何理解隔离性2(原理)
  • 题海拾贝:P2347 [NOIP 1996 提高组] 砝码称重
  • 【计网】SW、GBN、SR、TCP
  • 【无人机】无人机UAV、穿越机FPV的概念介绍,机型与工具,证书与规定
  • 【算法题】最长回文子串
  • RAG-Gym:一个用于优化带过程监督的代理型RAG的统一框架
  • C++语法系列之IO流
  • 重温经典算法——希尔排序
  • C语言数组初始化方法大全(附带实例)
  • 高速PCB设计中圆弧布线是否必要
  • ApacheSuperset CVE-2023-27524
  • L1-019 谁先倒 (15 分)
  • 慢SQL调优(二):大表查询
  • 《Offer来了:Java面试核心知识点精讲》大纲
  • 10. MySQL索引
  • Android apk装机编译类型: verify、speed-profile, speed与启动耗时
  • BUU MISC(持续更新)
  • [Java 基础]面向对象-继承
  • 得力Deli GE330W打印机信息
  • 如何流畅播放体育电竞赛事?
  • 三角形类CTriangle
  • python打卡day44
  • day 44
  • 【Bluedroid】蓝牙启动之gatt_init 流程源码解析
  • NLP学习路线图(二十二): 循环神经网络(RNN)