【力扣-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]和k=3：

• 窗口[1,3,-1]时队列存储[3,-1]的索引，最大值为3
• 窗口[3,-1,-3]时最大值仍为3
• 后续窗口依次输出[5,5,6,7]

扩展应用场景

该算法模式适用于：

• 所有滑动窗口极值问题
• 需要快速查询区间最大/最小值的场景
• 结合单调栈解决更复杂的区间问题