LeetCode739-DailyTemperatures

题目：根据每日温度列表，请重新生成一个列表，对应位置的输入是你需要等待多长时间，温度上升超过当天的天数。如果以后没有人提出，请在该位置使用0代替。例如，给定一个列表temperatures=[73,74,75,71,69,72,76,73]，您的输出应该是[1,1,4,2,1,1,0,0]。给定每日温度T的列表，返回一个列表，对于输入中的每一天，告诉您必须等待多少天才能变暖。如果没有可能的未来日期，请改为输入0。例如，给定温度列表T=[73,74,75,71,69,72,76,73]，您的输出应该是[1,1,4,2,1,1,0,0]。提示：温度列表长度范围为[1,30000]。每个温度的值都以华氏度为单位，整数在[30,100]范围内。注意：温度的长度将在[1,30000]范围内。每个温度都是[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]栈顶温度对应index7T[7]=76,76>73,index7pops出栈，this栈为空时，res[6]=0。索引6入栈，stack=[6]第三次遍历：i=5,T[i]=72,stack=[6]栈顶温度T[6]=76,72<76对应索引6，满足Request，当前索引5入栈。res[5]=stacktopindex6-currentindex5=1,stack=[6,5]第四次遍历：i=4,T[i]=69,stack=[6,5]对应的indexstacktop5的温度为T[5]=72，69<72，满足要求，将当前索引4入栈。res[4]=stacktopindex5-currentindex4=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]=stacktopindex5-currentindex3=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]=stacktopindex6-currentindex2=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]top对应的温度栈的T[1]=74，满足要求，当前索引0入栈。res[0]=1-0=1,stack=[6,2,1,0]遍历结束：res=[1,1,4,2,1,1,0,0]在这个方法中，stack中存储的索引对应的温度值，总是按照升序排列的。当栈为空时，证明当前温度是从这个温度开始的所有温度中最大的。Java:classSolution{publicint[]dailyTemperatures(int[]T){intlen=T.length;int[]res=newint[len];Stackstack=newStack<>();//初始化堆栈for(inti=len-1;i>=0;i--){while(!stack.isEmpty()&&T[stack.peek()]<=T[i]){stack.pop();}如果(stack.isEmpty())res[i]=0;否则res[i]=stack.peek()-i;堆栈.推（我）；}返回资源；这不是问题的好方法，因为提示已经明确指定了数据范围：列表长度的范围是[1,30000]。每个温度的值都以华氏度为单位，整数在[30,100]范围内。最多30000个数据量，数据很小，压栈，出栈，获取栈顶元素，判断栈是否为空。当数据量较小时，这些函数会被反复调用，相对来说会占用大量的运行时间。最终评估运行总时间为109毫秒。那么如何优化呢？由于所有数据值都在30到100范围内，因此用于按升序对温度进行排序的堆栈大小不能超过71（因为从30到100只有71个元素）。那么就不需要栈这种需要反复调用函数的数据结构了。就用一个长度为71的数组按顺序存放索引，定义一个指针，索引减一而不是弹出，索引加一赋值而不是入栈，索引是否溢出而不是判断栈是否为空，没有调用虚函数。优化后：总运行时间4ms，减少105msclassSolution{publicint[]dailyTemperatures(int[]T){intlen=T.length;int[]res=newint[len],stack=newint[71];整数指数=-1;对于(inti=len-1;i>=0;i--){while(index>=0&&T[stack[index]]<=T[i]){index--;}if(index>=0)res[i]=stack[index]-i;堆栈[++索引]=我；}返回资源；}}Python：Python没有队列和栈数据结构，因为数组可以做先进先出和后进先出等操作。类解决方案：defdailyTemperatures(self,T:List[int])->List[int]:tLen=len(T)stack=[]res=[0]*tLenforiinrange(tLen-1,-1,-1):whilestackandT[i]>=T[stack[-1]]:stack.pop()ifstack:res[i]=stack[-1]-istack.append(i)返回res欢迎关注微信。新工。一起学习的公众号：爱写bug