网站投资多少钱,制作做的网站如何上传网上,哈尔滨线下教学最新情况,wordpress 邮箱验证码【单调栈】No. 0739 每日温度 【中等】#x1f449;力扣对应题目指路 希望对你有帮助呀#xff01;#xff01;#x1f49c;#x1f49c; 如有更好理解的思路#xff0c;欢迎大家留言补充 ~ 一起加油叭 #x1f4a6; ⭐ 题目描述#xff1a;给定一个整数数组 temperatu…【单调栈】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(slow1, len(temperatures)):if temperatures[fast] temperatures[slow]:result[slow] fast-slowbreakreturn result 希望对你有帮助呀 如有更好理解的思路欢迎大家留言补充 ~ 一起加油叭 LeetCode 热题 HOT 100
