梅州哪里做网站,怎么做物流网站,安卓市场官方版,小制作手工视频739. 每日温度
请根据每日 气温 列表#xff0c;重新生成一个列表。对应位置的输出为#xff1a;要想观测到更高的气温#xff0c;至少需要等待的天数。如果气温在这之后都不会升高#xff0c;请在该位置用 0 来代替。
例如#xff0c;给定一个列表 temperatures [73, …739. 每日温度
请根据每日 气温 列表重新生成一个列表。对应位置的输出为要想观测到更高的气温至少需要等待的天数。如果气温在这之后都不会升高请在该位置用 0 来代替。
例如给定一个列表 temperatures [73, 74, 75, 71, 69, 72, 76, 73]你的输出应该是 [1, 1, 4, 2, 1, 1, 0, 0]。
提示气温 列表长度的范围是 [1, 30000]。每个气温的值的均为华氏度都是在 [30, 100] 范围内的整数。 这个题目是单调栈的入门题目看起其实很简单第一反应就是直接用一个双层循环就可以结束了。所以就引入了单调栈。单调栈解决的问题场景
那有同学就问了我怎么能想到用单调栈呢 什么时候用单调栈呢
通常是一维数组要寻找任一个元素的右边或者左边第一个比自己大或者小的元素的位置此时我们就要想到可以用单调栈了。时间复杂度为O(n)。
单调栈的本质是用空间换时间在本题中我们用栈来记录右边第一个比当前元素高的元素。
使用单调栈需要明确以下几点
1. 单调栈里面存放的元素是什么
在本题中单调栈里面存放元素的下标就可以了如果需要对应的元素直接T[i] 就可以获取
2. 单调栈里面的元素是递增的还是递减的
这里的顺序是指从栈头到栈底的顺序
这里我们使用递增的顺序。为什么因为只有递增的时候栈里要加入一个元素i的时候才知道栈顶元素在数组中右面第一个比栈顶元素大的元素是i。即如果求一个元素右边第一个更大元素单调栈就是递增的如果求一个元素右边第一个更小元素单调栈就是递减的。
使用单调栈主要有三个判断条件。
- 当前遍历元素小于栈顶元素
- 当前遍历元素等于栈顶元素
- 当前遍历元素大于栈顶元素
分析好了这三种情况问题也就差不多解决了。
1. 如果当前元素小于栈顶元素 我们应该让他入栈
2. 如果当前元素等于栈顶元素 因为我们求的是大于这里也应该直接入栈
3. 如果当前元素大于栈顶元素 那么此时我们就该弹出栈顶元素 并将当前元素的索引添加进对应的栈顶元素索引的结果 并pop掉当前元素 而且我们使用while循环将后续满足条件的进行相同操作 最后再讲当前i元素添加进栈顶
class Solution:def dailyTemperatures(self, temperatures: List[int]) - List[int]:stack [0]res [0] * len(temperatures)for i in range(1, len(temperatures)):if stack and temperatures[i] temperatures[stack[-1]]:stack.append(i)elif stack and temperatures[i] temperatures[stack[-1]]:stack.append(i)else:while stack and temperatures[i] temperatures[stack[-1]]:res[stack[-1]] i - stack[-1]stack.pop()stack.append(i)return res496.下一个更大元素 I
给你两个 没有重复元素 的数组 nums1 和 nums2 其中nums1 是 nums2 的子集。
请你找出 nums1 中每个元素在 nums2 中的下一个比其大的值。
nums1 中数字 x 的下一个更大元素是指 x 在 nums2 中对应位置的右边的第一个比 x 大的元素。如果不存在对应位置输出 -1 。
这个题呢和上面的题非常类似而且是不重复的数字我们将nums1 建立字典然后求出整体的然后再映射回去。
class Solution:def nextGreaterElement(self, nums1: List[int], nums2: List[int]) - List[int]:from collections import defaultdictmap_ defaultdict(int)res []stack [nums2[0]]for i in range(len(nums2)):if nums2[i] stack[-1]:stack.append(nums2[i])else:while stack and nums2[i] stack[-1]:map_[stack[-1]] nums2[i]stack.pop()stack.append(nums2[i])for num in nums1:if map_.get(num):res.append(map_[num])else:res.append(-1)return res503.下一个更大元素II
给定一个循环数组最后一个元素的下一个元素是数组的第一个元素输出每个元素的下一个更大元素。数字 x 的下一个更大的元素是按数组遍历顺序这个数字之后的第一个比它更大的数这意味着你应该循环地搜索它的下一个更大的数。如果不存在则输出 -1。
示例 1:
输入: [1,2,1]输出: [2,-1,2]解释: 第一个 1 的下一个更大的数是 2数字 2 找不到下一个更大的数第二个 1 的下一个最大的数需要循环搜索结果也是 2。
这个题呢与与每日温度最大的不同在于他是循环的数组。一个很直观的想法就是将数组拼接起来然后使用单调栈求下一个最大值。将两个nums数组拼接在一起使用单调栈计算出每一个元素的下一个最大值最后再把结果集即result数组resize到原数组大小就可以了。 但是也可以不扩展nums 而是在遍历的过程中模拟走两遍nums.
如果走两遍nums呢使用i%len(nums)
且遍历的元素是在0, len(nums) * 2
class Solution:def nextGreaterElements(self, nums: List[int]) - List[int]:stack []res [-1] * len(nums)for i in range(len(nums)*2):while (len(stack) ! 0 and nums[i%len(nums)] nums[stack[-1]]):res[stack[-1]] nums[i%len(nums)]stack.pop()stack.append(i%len(nums))return res
