用途
维持求解答案的可能性(包括 维持滑动窗口中的最大值或最小值)
核心原理
长江后浪推前浪——用最新最好的可能性淘汰最差最旧的可能性
in other words,讨论可能性的价值与时效性
基本用法
分析可能性,若推出的可能性集合中有单调性
从队头和队尾考虑没有价值的可能性
错题
LeetCode 1438. 绝对差不超过限制的最长连续子数组
错误想法:用了两个队列,分别维护最小值和最大值,检查有无超过限制,若没超过记录答案,若超过比较两者在num数组里的位置,将靠前的从队头出队
错因:这里很明显把某些答案漏掉了
思路引领:观察题目,这道题比较容易看出是找各种可能的题目,所以考虑可能性
从i开始,考虑以i为开头的最长能扩到的子数组,这里可以发现,要满足条件的话就要记录这一段的最小值和最大值,且范围扩大,最小值肯能更小,最大值可能更大,反之亦然。因此我们可以发现这个是有单调性的,进而想到滑动窗口这个逻辑
大体流程就是,r进来看能不能扩,如果能扩就扩,不能扩结算l这个位置的答案,然后将l从队列里弹出(如果在头部就弹出,不可能在尾部,因为它是最早的)
LeetCode 2071. 你可以安排的最多任务数目(这里队列的单调性不是很明显)
错误想法:没思路,尝试过每个工人完成离ta最近的任务,但又因为如果吃了药这样的话可能很浪费,所以不可行
思路引领:观察题目,由于有药片参与很难直接解决,但是发现“最多”,属于最优化问题,加之我们可以判定任务数量的范围,且具有单调性,check函数相对容易,所以进行二分答案
现在重点考虑check函数,(如果有m个任务,那么这么多药片能否完成)
首先给task和worker排个序,那么check里面就是前m个任务和后m个工人,考虑工人i做的任务,要一下可能性
1)不用药物可以满足的
2)用药物可以满足的,那么做能做任务中消耗值最大的那个
3)用药物也不满足,false
这里会发现有指针回退的情况,为了避免,我们可以把能解锁的任务都解锁存在队列里,如果x不能解锁任务,从队列里找,如果还不行,服用药物找,那么就可以写成
1)不用药物,解锁任务
2)不用药物,从队列里找出头部做任务
3)服用药物,解锁任务,然后从队列末尾找出要做的任务
4)服用药物仍然不行,return false
算法:二分+贪心+单调队列
总结
不要把队列限制到值里面,队列其实就是可能性的策略集合,只要可能性中存在单调性,就可以利用单调队列