单调队列-解定长滑窗的最值问题 ( leetcode 239)

引言

碎碎念，找了很多关于单调队列的说明，但是感觉都不是很本质且直击要害，很多都是在讲算法过程本身，这里贴一下算法思想和代码实现。

leetcode 239 求定长滑动窗口的最大值链接

核心思想为定义并维护下面的循环不变式：

每次循环开始前，队列中的元素为【上一个窗口】的所有元素中大于等于窗口右端点元素值的元素按照降序排列得到的序列的一个【非空子序列】，并规定除了最大值元素和右端点元素外，中间元素允许缺失！

代码，参考了链接

classSolution:defmaxSlidingWindow(self,nums:List[int],k:int)->List[int]:ans=[0]*(len(nums)-k+1)# 窗口个数q=deque()# 双端队列# 核心循环不变式：每次循环开始前，队列中的元素为【上一个窗口】的所有元素中，# 大于等于窗口右端点元素值的元素按照降序排列得到的序列的一个【非空子序列】，# 并规定除了最大值元素和右端点元素外，中间元素允许缺失！（这个是针对第一个窗口的补丁）fori,xinenumerate(nums):# 计算当前滑窗的左端点left=i-k+1# 下面的1,2操作维护当前轮窗口的循环不变式# 1.左边出# 判断上一个窗口的最大值元素是否恰好为上一个窗口的左边界元素：# 如果是，则需要从当前窗口移出，因为窗口整体右移了1位 （注意只有i >=k 才有移出左边界的操作）# 如果不是，不需要进行任何操作ifi>=kandq[0]==left-1:q.popleft()# 2. 右边入，将破坏当前轮循环不变式的元素pop出# 然后再加入当前元素的下标whileqandnums[q[-1]]<=x:q.pop()q.append(i)# 注意保存的是下标# 3. 记录答案ifleft>=0:# 由于队首到队尾单调递减，所以窗口最大值就在队首ans[left]=nums[q[0]]returnans

启发，部分重叠问题都可以从维护循环不变式的角度进行思考构建算法。