金属材料东莞网站建设,wordpress恋月,济源网站开发,制作图片的app免费目录 739. 每日温度思路代码 496.下一个更大元素 I思路代码 739. 每日温度
Leetcode 思路
维持一个单调递增的栈#xff0c;向栈逐一pushtemperatures里的index。
如果当前遍历的元素大于栈顶元素#xff0c;这意味着 栈顶元素的 右边的最大的元素就是 当前遍历的元素向栈逐一pushtemperatures里的index。
如果当前遍历的元素大于栈顶元素这意味着 栈顶元素的 右边的最大的元素就是 当前遍历的元素所以弹出 栈顶元素并记录否则的话可以直接入栈。
代码
class Solution:def dailyTemperatures(self, temperatures: List[int]) - List[int]:stack [0]answer [0] * len(temperatures)for i in range(1, len(temperatures)):if temperatures[i] temperatures[stack[-1]]:stack.append(i)else:while len(stack) ! 0 and temperatures[i] temperatures[stack[-1]]:answer[stack[-1]] i - stack[-1]stack.pop()stack.append(i)return answer时间复杂度O(n)空间复杂度O(n)
496.下一个更大元素 I
Leetcode 思路
这道题和上一题类似。
维护一个nums2的单调递增栈只不过在pop的时候需要在nums1中寻找相应的index这一步可以用.index()也可以使用哈希表。
代码
.index()
class Solution:def nextGreaterElement(self, nums1: List[int], nums2: List[int]) - List[int]:res [-1] * len(nums1)stack [0]for i in range(len(nums2)):if nums2[i] nums2[stack[-1]]:stack.append(i)else:while stack and nums2[i] nums2[stack[-1]]:if nums2[stack[-1]] in nums1:index nums1.index(nums2[stack[-1]])res[index] nums2[i]stack.pop()stack.append(i)return res哈希表
class Solution:def nextGreaterElement(self, nums1: List[int], nums2: List[int]) - List[int]:res [-1] * len(nums1)stack [0]dic {}for i, v in enumerate(nums1):dic[v] ifor i in range(len(nums2)):if nums2[i] nums2[stack[-1]]:stack.append(i)else:while stack and nums2[i] nums2[stack[-1]]:if nums2[stack[-1]] in nums1:index dic[nums2[stack[-1]]]res[index] nums2[i]stack.pop()stack.append(i)return res
