大橙子网站建设,新征程启航
为企业提供网站建设、域名注册、服务器等服务
这篇文章给大家介绍Python中如何根据每日温度生成一个列表,内容非常详细,感兴趣的小伙伴们可以参考借鉴,希望对大家能有所帮助。
创新互联公司是专业的北林网站建设公司,北林接单;提供做网站、网站建设,网页设计,网站设计,建网站,PHP网站建设等专业做网站服务;采用PHP框架,可快速的进行北林网站开发网页制作和功能扩展;专业做搜索引擎喜爱的网站,专业的做网站团队,希望更多企业前来合作!
今天的Python学习教程:根据每日温度生成一个列表,也算是一个实操训练,伙伴们可以一起动手操练起来了!
根据每日 气温 列表,请重新生成一个列表,对应位置的输入是你需要再等待多久温度才会升高超过该日的天数。如果之后都不会升高,请在该位置用 0 来代替。
例如,给定一个列表 temperatures = [73, 74, 75, 71, 69, 72, 76, 73],你的输出应该是 [1, 1, 4, 2, 1, 1, 0, 0]。
Given a list of daily temperatures T, return a list such that, for each day in the input, tells you how many days you would have to wait until a warmer temperature. If there is no future day for which this is possible, put 0 instead.
For example, given the list of temperatures T = [73, 74, 75, 71, 69, 72, 76, 73], your output should be [1, 1, 4, 2, 1, 1, 0, 0].
提示:气温 列表长度的范围是 [1, 30000]。每个气温的值的均为华氏度,都是在 [30, 100] 范围内的整数。
Note: The length of temperatures will be in the range [1, 30000]. Each temperature will be an integer in the range [30, 100].
解题思路:
最容易想到和理解的就是暴力穷举,两个指针,一个指针指向当前温度,第二指针向后遍历找到最近一个比当前温度高的温度,记录两个指针的索引差即可。可以说效率非常低了。
另一种方法是借助栈倒序遍历原数组,存入较高的温度的索引,也很容易理解,时间复杂度为 O(n)。其实现逻辑为:
原数组:[73, 74, 75, 71, 69, 72, 76, 73],指针 i 从末尾向前遍历,返回数组res=[0,0,0,0,0,0,0] 第一次遍历: i = 7, T[i] = 73, stack = [] 栈为空,res[7] = 0 ,73所在索引7入栈。stack = [7] 第二次遍历: i = 6, T[i] = 76, stack = [7] 栈顶对应索引7的温度T[7]=76,76>73,索引7出栈,此时栈为空,res[6] = 0。索引6入栈,stack = [6] 第三次遍历: i = 5, T[i] = 72, stack = [6] 栈顶对应索引6的温度T[6]=76,72<76,满足要求,当前索引5入栈。res[5] = 栈顶索引6 - 当前索引5 = 1, stack = [6,5] 第四次遍历: i = 4, T[i] = 69, stack = [6,5] 栈顶对应索引5的温度T[5]=72,69<72,满足要求,当前索引4入栈。res[4] = 栈顶索引5-当前索引4=1, stack = [6,5,4] 第五次遍历: i = 3, T[i] = 71, stack = [6,5,4] 栈顶对应索引的温度T[4]=69,71>69,栈顶元素出栈。stack = [6,5] 栈顶对应索引的温度T[5]=72,满足要求,当前索引3入栈。res[3] = 栈顶索引5-当前索引3=2, stack = [6,5,3] 第六次遍历: i = 2, T[i] = 75, stack = [6,5,3] 栈顶对应索引的温度T[3]=71,75>71,栈顶元素出栈。stack = [6,5] 栈顶对应索引的温度T[5]=72,75>72,栈顶元素出栈。stack = [6] 栈顶对应索引的温度T[6]=76,75<76,满足要求,当前索引2入栈。res[2] = 栈顶索引6-当前索引2=4, stack = [6,2] 第七次遍历: i = 1, T[i] = 74, stack = [6,2] 栈顶对应的温度T[2]=75,满足要求,当前索引1入栈。res[1] = 2-1=1, stack = [6,2,1] 第八次遍历: i = 0, T[i] = 73, stack = [6,2,1] 栈顶对应的温度T[1]=74,满足要求,当前索引0入栈。res[0] = 1-0=1, stack = [6,2,1,0] 遍历结束: res = [1,1,4,2,1,1,0,0]
这种方法下,栈存入索引对应的温度值始终按升序排列,当栈为空时,证明当前温度为 从该温度向后的所有温度里 最大的。
Java:
class Solution { public int[] dailyTemperatures(int[] T) { int len=T.length; int[] res = new int[len]; Stackstack = new Stack<>();//初始化栈 for (int i = len - 1; i >= 0; i--) { while (!stack.isEmpty() && T[stack.peek()] <= T[i]) { stack.pop(); } if (stack.isEmpty()) res[i] = 0; else res[i] = stack.peek() - i; stack.push(i); } return res; } }
事实上就这道题而言这并不是一个好方法,因为提示已经明确规定了数据范围:
列表长度的范围是 [1, 30000]。每个气温的值的均为华氏度,都是在 [30, 100] 范围内的整数。
最多30000个数据量,数据非常小,入栈出栈,获取栈顶元素,判断栈是否空,在数据量很少的情况下这些函数反复调用,相对就占用了很多运行时间,其最终评测运行总时间为 109 ms。那么如何优化?
由于所有数据值的范围均在30到100之间,那么意为着按升序排列温度的栈的大小 最大不会超过71(因为从30到100只有71个元素)。那就可以不用栈这个需要反复调用函数的数据结构。直接用长度为71的数组顺序存入索引即可,定义一个指针,索引减一代替出栈,索引加一并赋值代替入栈,索引是否溢出代替判断栈是否为空,无虚函数调用。
优化后:
总运行时间为 4ms,降低了105毫秒
class Solution { public int[] dailyTemperatures(int[] T) { int len = T.length; int[] res = new int[len], stack = new int[71]; int index = -1; for (int i = len - 1; i >= 0; i--) { while (index >= 0 && T[stack[index]] <= T[i]) { index--; } if(index >= 0) res[i] = stack[index] - i; stack[++index] = i; } return res; } }
Python:
python并没有队列、栈这种数据结构,因为数组就可以做到先进先出、后进先出等操作。
class Solution: def dailyTemperatures(self, T: List[int]) -> List[int]: tLen = len(T) stack = [] res = [0] * tLen for i in range(tLen - 1, -1, -1): while stack and T[i] >= T[stack[-1]]: stack.pop() if stack: res[i] = stack[-1] - i stack.append(i) return res
关于Python中如何根据每日温度生成一个列表就分享到这里了,希望以上内容可以对大家有一定的帮助,可以学到更多知识。如果觉得文章不错,可以把它分享出去让更多的人看到。