引言碎碎念找了很多关于单调队列的说明但是感觉都不是很本质且直击要害很多都是在讲算法过程本身这里贴一下算法思想和代码实现。leetcode 239 求定长滑动窗口的最大值链接核心思想为定义并维护下面的循环不变式每次循环开始前队列中的元素为【上一个窗口】的所有元素中大于等于窗口右端点元素值的元素按照降序排列得到的序列的一个【非空子序列】并规定除了最大值元素和右端点元素外中间元素允许缺失代码参考了链接classSolution:defmaxSlidingWindow(self,nums:List[int],k:int)-List[int]:ans[0]*(len(nums)-k1)# 窗口个数qdeque()# 双端队列# 核心循环不变式每次循环开始前队列中的元素为【上一个窗口】的所有元素中# 大于等于窗口右端点元素值的元素按照降序排列得到的序列的一个【非空子序列】# 并规定除了最大值元素和右端点元素外中间元素允许缺失这个是针对第一个窗口的补丁fori,xinenumerate(nums):# 计算当前滑窗的左端点lefti-k1# 下面的1,2操作维护当前轮窗口的循环不变式# 1.左边出# 判断上一个窗口的最大值元素是否恰好为上一个窗口的左边界元素# 如果是则需要从当前窗口移出因为窗口整体右移了1位 注意只有i k 才有移出左边界的操作# 如果不是不需要进行任何操作ifikandq[0]left-1:q.popleft()# 2. 右边入将破坏当前轮循环不变式的元素pop出# 然后再加入当前元素的下标whileqandnums[q[-1]]x:q.pop()q.append(i)# 注意保存的是下标# 3. 记录答案ifleft0:# 由于队首到队尾单调递减所以窗口最大值就在队首ans[left]nums[q[0]]returnans启发部分重叠问题都可以从维护循环不变式的角度进行思考构建算法。