成都网站外包优化,软件开发合同模板,h5设计软件,备案成功的网站739. 每日温度
给定一个整数数组 temperatures #xff0c;表示每天的温度#xff0c;返回一个数组 answer #xff0c;其中 answer[i] 是指对于第 i 天#xff0c;下一个更高温度出现在几天后。如果气温在这之后都不会升高#xff0c;请在该位置用 0 来代替
思路#…739. 每日温度
给定一个整数数组 temperatures 表示每天的温度返回一个数组 answer 其中 answer[i] 是指对于第 i 天下一个更高温度出现在几天后。如果气温在这之后都不会升高请在该位置用 0 来代替
思路
这种求数组元素左右的第一个大于小于当前元素的类型适合用单调栈来做。
单调栈的单调属性单调递增栈头到栈尾从小到大排列。
单调栈存放元素内容第几天
遍历时的情况当前天数的温度大于栈头天数温度时将栈头元素出栈当前当前天数与栈头天数的差值就是栈头天数的下一个温度出现所需天数然后继续比较。当前天数温度小于等于栈头天数温度时将元素入栈遍历下一天。
class Solution:def dailyTemperatures(self, temperatures):result [0 for _ in range(len(temperatures))]stack [0]for i, v in enumerate(temperatures[1:]):if v temperatures[stack[-1]]:stack.append(i 1)else:while stack and v temperatures[stack[-1]]:result[stack[-1]] i 1 - stack[-1]stack.pop()stack.append(i 1)return result496. 下一个更大元素 I
nums1 中数字 x 的 下一个更大元素 是指 x 在 nums2 中对应位置 右侧 的 第一个 比 x 大的元素。
给你两个 没有重复元素 的数组 nums1 和 nums2 下标从 0 开始计数其中nums1 是 nums2 的子集。
对于每个 0 i nums1.length 找出满足 nums1[i] nums2[j] 的下标 j 并且在 nums2 确定 nums2[j] 的 下一个更大元素 。如果不存在下一个更大元素那么本次查询的答案是 -1 。
返回一个长度为 nums1.length 的数组 ans 作为答案满足 ans[i] 是如上所述的 下一个更大元素 。
思路依然是单调栈
class Solution:def nextGreaterElement(self, nums1: List[int], nums2: List[int]) - List[int]:stack [nums2[0]]ans [-1 for _ in range(len(nums1))]for i in nums2[1:]:if i stack[-1]:stack.append(i)else:while stack and i stack[-1]:if stack[-1] in nums1:index nums1.index(stack[-1])ans[index] istack.pop()stack.append(i)return ans
