OPEN17的个人小站
基算精讲(27)-单调队列
基本模板思想
stateDiagram
A:及时去掉无用数据,保持双端队列有序
direction LR
A --> 当新的数值优/等于队尾,弹出队尾: 类同单调栈(循环)
A --> 弹出队首不在窗口内的元素
视频链接
算法基础精讲
那些算法究竟是怎么想出来的？灵神将带你知其然，更知其所以然！
练习
滑动窗口最大值
链接
写法1
仔细想想为什么要存下标而不是值呢?
class Solution:
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
ans=[]
q=deque()
for i,x in enumerate(nums):
# 小于或者小于等于都行
while q and nums[q[-1]]<=x:
q.pop()
q.append(i)
if i-q[0]+1>k:
q.popleft()
if i>=k-1:
ans.append(nums[q[0]])
return ans
写法2,注意为什么一定要是小于不能是小于等于呢
class Solution:
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
ans=[]
q=deque()
l=0
for i,x in enumerate(nums):
while q and q[-1]<x:
q.pop()
q.append(x)
if i-l+1>k:
if nums[l]==q[0]:
q.popleft()
l+=1
if i>=k-1:
ans.append(q[0])
return ans
绝对差不超过限制的最长连续子数组
一般来说,处理滑动窗口相同值的弹出有两种思路:
- 入窗的时候可以不保留相同值,然后记录的是下标,一般需要滑窗定长(不维护l)
- 或者保留相同值,然后记录的left,当a[left]等于值的时候就弹出
class Solution:
def longestSubarray(self, nums: List[int], limit: int) -> int:
ans=0
max_q=deque()
min_q=deque()
l=0
for i,x in enumerate(nums):
while max_q and nums[max_q[-1]]<x:
max_q.pop()
while min_q and nums[min_q[-1]]>x:
min_q.pop()
max_q.append(i)
min_q.append(i)
while max_q and min_q and abs(nums[max_q[0]]-nums[min_q[0]])>limit:
if max_q[0]==l:
max_q.popleft()
if min_q[0]==l:
min_q.popleft()
l+=1
ans=max(i-l+1,ans)
return ans
预算内的最多机器人数目
单调队列一般用于维护滑动窗口的最值,本题维护一个正常的滑窗值和+维护最值即可
题外话
如何证明滑动窗口的正确性呢?记住一点,上一次是恰好符合/不符合答案的边界情况,左指针往左移就不满足条件了,现在右指针扩大了,左指针往左移更不可能满足条件
class Solution:
def maximumRobots(self, chargeTimes: List[int], runningCosts: List[int], budget: int) -> int:
s=0
q=deque()
l=0
ans=0
for r,v in enumerate(chargeTimes):
while q and q[-1]<v:
q.pop()
q.append(v)
s+=runningCosts[r]
while q and s*(r-l+1)+q[0]>budget:
if chargeTimes[l]==q[0]:
q.popleft()
s-=runningCosts[l]
l+=1
ans=max(ans,r-l+1)
return ans
和至少为 K 的最短子数组
太妙啦!求和找不到单调性?前缀和转为找单点极值!然后枚举右端点单调队列维护单点极值即可
为什么可以使用滑动窗口寻找?因为除了求和的大小满足大于k我们还需要子数组最短
class Solution:
def shortestSubarray(self, nums: List[int], k: int) -> int:
a=[0]
for i in nums:
a.append(a[-1]+i)
ans=inf
min_q=deque()
l=0
for r,v in enumerate(a):
while min_q and min_q[-1]>v:
min_q.pop()
min_q.append(v)
while min_q and v-min_q[0]>=k:
ans=min(ans,r-l)
if a[l]==min_q[0]:
min_q.popleft()
l+=1
return ans if ans!=inf else -1
满足不等式的最大值
跳跃游戏 VI
链接
购买水果需要的最少金币数
带限制的子序列和
链接
总结
...