新手学做网站学要做哪些,wordpress增加说说,一流的医疗网站建设,北京网站建设公司网络营销外包网络建站报价单调栈#xff1a;每日温度
请根据每日 气温 列表 temperatures #xff0c;请计算在每一天需要等几天才会有更高的温度。如果气温在这之后都不会升高#xff0c;请在该位置用 0 来代替单调栈基本只处理NGE问题#xff08;Next GreaterElement#xff09;。对序列中每个元…单调栈每日温度
请根据每日 气温 列表 temperatures 请计算在每一天需要等几天才会有更高的温度。如果气温在这之后都不会升高请在该位置用 0 来代替单调栈基本只处理NGE问题Next GreaterElement。对序列中每个元素找到下一个比它大的元素。“下一个”可以换成“上一个”“大”也可以换成“小”
class Solution(object):def dailyTemperatures(self, temperatures)::type temperatures: List[int]:rtype: List[int]length len(temperatures)res [0 for _ in range(length)]stack [] # 维护一个单调栈其中的值是单调递减的for i in range(length):t temperatures[i]while (len(stack) 0 and temperatures[stack[-1]] t):res[stack[-1]] i - stack[-1]stack.pop()stack.append(i)return res单调队列滑动窗口的最大值 给定一个数组 nums 和滑动窗口的大小 k请找出所有滑动窗口里的最大值典型用法 详细参考 用一个queue滑动窗口先入先出和一个deque实现
queue负责push和popdeque用来存放最大值
1. 如果新的value大于deque尾端的值那么deque一直进行pop_back操作直到尾端的值大于等于value 或者为空再将value压入deque的尾部
2. 每次取max_value返回deque首部的值
3. 当que进行pop操作时如果que首部的值等于deque首部的值那么deque同样需要进行pop_front操作class Solution(object):def maxSlidingWindow(self, nums, k)::type nums: List[int]:type k: int:rtype: List[int]desc_q [] # 单调递减队列# 初始化for i in range(k):while (desc_q and desc_q[-1] nums[i]):desc_q.pop()desc_q.append(nums[i])res [desc_q[0]]for i in range(k, length):in_num nums[i] # 加入窗口的数字out_num nums[i - k] # 退出窗口的数字if out_num desc_q[0]: # 如果在单调队列首部则同步退出desc_q.pop(0)while (desc_q and desc_q[-1] in_num):desc_q.pop()desc_q.append(in_num)res.append(desc_q[0])return res
