【力扣-239. 滑动窗口最大值[特殊字符]】Python笔记

单调队列与滑动窗口算法详解滑动窗口概念滑动窗口技术用于在数组或字符串上维护一个固定大小的子区间。传统暴力解法每次滑动窗口后重新计算极值会导致O(nk)时间复杂度在数据规模较大时效率低下。单调队列特性单调队列通过特殊结构保证队列元素始终有序队列元素按从大到小排列队首最大新元素入队前会移除队尾所有较小元素自动清理超出窗口范围的过期元素获取极值时间复杂度为O(1)算法实现步骤初始化双端队列和结果列表。遍历数组时执行三个关键操作维护队列单调性移除队尾所有小于当前元素的索引检查并移除超出窗口范围的队首元素当窗口形成后记录队首元素对应的值代码示例from collections import deque def maxSlidingWindow(nums, k): q deque() result [] for i in range(len(nums)): while q and nums[q[-1]] nums[i]: q.pop() q.append(i) if q[0] i - k: q.popleft() if i k - 1: result.append(nums[q[0]]) return result复杂度分析时间复杂度严格线性每个元素最多入队出队各一次总体时间复杂度O(n) 空间复杂度取决于窗口大小队列最多存储k个元素空间复杂度O(k)实际应用示例给定数组[1,3,-1,-3,5,3,6,7]和k3窗口[1,3,-1]时队列存储[3,-1]的索引最大值为3窗口[3,-1,-3]时最大值仍为3后续窗口依次输出[5,5,6,7]扩展应用场景该算法模式适用于所有滑动窗口极值问题需要快速查询区间最大/最小值的场景结合单调栈解决更复杂的区间问题