您的位置:首页 > 游戏 > 手游 > LeetCode 热题 HOT 100 (004/100)【宇宙最简单版】

LeetCode 热题 HOT 100 (004/100)【宇宙最简单版】

2024/12/23 2:26:10 来源:https://blog.csdn.net/CODE_RabbitV/article/details/140583726  浏览:    关键词:LeetCode 热题 HOT 100 (004/100)【宇宙最简单版】

【单调栈】No. 0739 每日温度 【中等】👉力扣对应题目指路

希望对你有帮助呀!!💜💜 如有更好理解的思路,欢迎大家留言补充 ~ 一起加油叭 💦
欢迎关注、订阅专栏 【力扣详解】谢谢你的支持!

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

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

🔥 思路:遍历一遍 temperatures, 后续一旦找到更大的值就填写对应的 result

  • 最直接的思路是暴力解法,但提交会超时,放在最后供友友们参考~
  • 用空间换时间:用单调栈存储当前尚未找到更大值的日期 (idx)

参考如上思路,给出详细步骤如下:

  • 步骤一⭐确定栈 stack 内元素含义:当前尚未找到更大值的日期 (idx)
  • 步骤二⭐编写遍历 temperatures 的代码框架
  • 步骤三⭐由顶逐个处理当前栈内元素 stack[-1]:若对应温度 temperatures[stack[-1]] 小于当前遍历到的 temperatures[i] 说明找到了满足要求的日期,则填写对应的 result result[stack[-1]]i - stack[-1];已找到则弹出
    • 为什么栈 stack 是单调的:比新栈顶元素 temperatures[i] 小的都会弹出 while stack and temperatures[stack[-1]] < temperatures[i],所以维护了单调栈
    • 为什么需要栈 stack 是单调的:
      • 否则小的温度可能被压在栈内(非栈顶),始终无法处理
      • 如果改用一般列表,对于 temperatures[i] 需要判断列表中存储的每个值 (超时⏳)
  • 步骤四⭐遍历到的 temperatures[i] 入栈 (仅记录 i 即可), 待后续处理
class Solution:def dailyTemperatures(self, temperatures: List[int]) -> List[int]:result = [0 for _ in temperatures]stack = []  ## 模拟单调栈  # ------------------------------------------step 1for i in range(len(temperatures)):  # --------------------------------step 2## 比新栈顶元素小的都会弹出,所以维护了单调栈while stack and temperatures[stack[-1]] < temperatures[i]:  # ----step 3result[stack[-1]] = i - stack[-1]stack.pop()  ## 出栈stack.append(i)  ## 入栈  # --------------------------------------step 4return result

复杂度分析

  • 时间复杂度:O(n),其中 n 是温度列表的长度
    • 正向遍历温度列表一遍,对于温度列表中的每个下标,最多有一次进栈和出栈的操作。
  • 空间复杂度:O(n),其中 n 是温度列表的长度
    • 需要维护一个单调栈存储温度列表中的下标。

⏳⏳⏳ 暴力解法来啦 ~ 提交会超时 !!!

class Solution:def dailyTemperatures(self, temperatures: List[int]) -> List[int]:result = [0 for _ in temperatures]for slow in range(len(temperatures)):for fast in range(slow+1, len(temperatures)):if temperatures[fast] > temperatures[slow]:result[slow] = fast-slowbreakreturn result                      

希望对你有帮助呀!!💜💜 如有更好理解的思路,欢迎大家留言补充 ~ 一起加油叭 💦
🔥 LeetCode 热题 HOT 100