题目 739 每日温度
给定一个整数数组 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]
思路
-
两个for循环可得到结果,时间复杂度是O(n^2)。
-
那么接下来在来看看使用单调栈的解法。
那有同学就问了,我怎么能想到用单调栈呢? 什么时候用单调栈呢?
通常是一维数组,要寻找任一个元素的右边或者左边第一个比自己大或者小的元素的位置,此时我们就要想到可以用单调栈了。时间复杂度为O(n)。
例如本题其实就是找找到一个元素右边第一个比自己大的元素。
具体单调栈的思路想法可以参考b站视频单调栈其实很简单,加上自己用笔在纸上画画,很容易就理解了,我们这里采用的是单调递增栈(从栈顶到栈底)。注意:不建议参考代码随想录,那里把问题有些复杂化了感觉。 -
代码里就考虑了两种情况,什么时候入栈,什么时候出栈且更新结果。当元素大于栈顶元素时,就出栈且更新结果,当元素小于栈顶元素时就直接入栈。至于代码里为什么考虑了栈是否为空,因为可能会出现元素会连续大于栈顶元素好多次,所以循环考虑。
代码
class Solution:
def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
stack = [0]
res = [0 for _ in range(len(temperatures))]
for i in range(len(temperatures)):
# 如果栈不为空且元素大于栈顶元素,更新结果,且出栈
while stack != [] and temperatures[i] > temperatures[stack[-1]]:
res[stack[-1]] = i - stack[-1]
stack.pop()
# 栈为空或者元素小于小于栈顶元素,就直接入栈
stack.append(i)
return res
原文地址:http://www.cnblogs.com/edkong/p/16852945.html
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,请务用于商业用途!
3. 如果你也有好源码或者教程,可以到用户中心发布,分享有积分奖励和额外收入!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需!
7. 如遇到加密压缩包,默认解压密码为"gltf",如遇到无法解压的请联系管理员!
8. 因为资源和程序源码均为可复制品,所以不支持任何理由的退款兑现,请斟酌后支付下载
声明:如果标题没有注明"已测试"或者"测试可用"等字样的资源源码均未经过站长测试.特别注意没有标注的源码不保证任何可用性