模板网站建设公司,wordpress情侣网站源码,苏州知名高端网站建设网络公司,一级a做爰片免费网站冫上一篇:算法随笔_34: 最后一个单词的长度-CSDN博客 题目描述如下:
给定一个整数数组 temperatures #xff0c;表示每天的温度#xff0c;返回一个数组 answer #xff0c;其中 answer[i] 是指对于第 i 天#xff0c;下一个更高温度出现在几天后。如果气温在这之后都不会升…上一篇:算法随笔_34: 最后一个单词的长度-CSDN博客 题目描述如下:
给定一个整数数组 temperatures 表示每天的温度返回一个数组 answer 其中 answer[i] 是指对于第 i 天下一个更高温度出现在几天后。如果气温在这之后都不会升高请在该位置用 0 来代替。
示例 1:
输入: temperatures [73,74,75,71,69,72,76,73]
输出: [1,1,4,2,1,1,0,0] 算法思路:
这道题的暴力解法是我们从左往右枚举temperatures[i]对于每一个temperatures[i]我们用第二层循环再枚举它之后的元素从而找到temperatures[i]的第一个更高的温度。第一层循环完成后即可返回答案。
接下来我们探讨一个更高效的算法单调栈解法。为了方便描述下面我们用tp代替temperatures数组res表示answer数组。我们用一个示例来解析一下算法背后的原理。我们假设tp有15个元素。让我们从左往右开始枚举数组。
1. 如果tp[1]大于tp[0]我们就找到了tp[0]的答案。
2. 如果tp[1]小于tp[0]我们需要查看tp[2]如果tp[2]大于tp[1]此时我们就找到了tp[1]的答案为tp[2]。
3. 如果tp[2]也大于tp[0]那么我们也找到了tp[0]的答案为tp[2]。
经过上面这3步的分析我们发现当温度连续递减的时候这些被访问过的元素都还没找到它们对应的答案。当递减之后温度第一次升高时如tp[5]。我们可以从右往左对于访问过的元素tp[0]tp[1]tp[2]tp[3]tp[4]再一次比较。此时可以依次找到部分元素的答案直到tp[5]小于某个已经访问过的元素为止。
根据此特征我们可以使用单调栈的思路来解决此问题。具体的算法如下:
1. 我们设一个临时数组stck做为单调栈stck初始元素为0。设结果数组res它的长度和tp数组一样初始每个元素为0。然后从左往右枚举数组tp。
2. 如果温度保持递减趋势我们把元素下标不断的放入数组stck中直到碰到第一次升高比如tp[i]。
3. 我们用tp[i]和stck的末尾元素即stck[-1]比较。如果stck[-1]小于元素tp[i]我们计算两个下标的距离并存入res数组对应的位置。然后弹出stck[-1]。重复步骤3直到碰到stck[-1]大于tp[i]我们把下标i放入stck中。
4. 继续枚举tp[i1]转到步骤3。直到枚举完数组tp。
如果stck中仍有元素说明这些元素不能找到更高的温度。相应的res位置因为初始值就为0所以无需处理这些元素。
此算法的时间复杂度为O(n) 。下面是代码实现:
class Solution(object):def dailyTemperatures(self, temperatures)::type temperatures: List[int]:rtype: List[int]tp_lenlen(temperatures)stck[0]res[0]*tp_lenfor i in range(1,tp_len):while len(stck)0 and temperatures[i]temperatures[stck[-1]]:res[stck[-1]]i-stck[-1]stck.pop()stck.append(i)return res
