Skip to main content

滑动窗口最大值

给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。

返回 滑动窗口中的最大值 。

示例 1：

输入：nums = [1,3,-1,-3,5,3,6,7], k = 3 输出：[3,3,5,5,6,7] 解释： 滑动窗口的位置 最大值

[1 3 -1] -3 5 3 6 7 3 1 [3 -1 -3] 5 3 6 7 3 1 3 [-1 -3 5] 3 6 7 5 1 3 -1 [-3 5 3] 6 7 5 1 3 -1 -3 [5 3 6] 7 6 1 3 -1 -3 5 [3 6 7] 7 示例 2：

输入：nums = [1], k = 1 输出：[1]

简单做法：遍历 + max取最大值

进阶做法：使用**双端队列（Deque）**来维护窗口内的最大值。双端队列中存储的是元素的索引，确保队列头部的索引对应的元素始终是当前窗口的最大值。

方法思路​

  1. 初始化双端队列：队列中存储元素的索引，保持队列头部元素对应的数值最大。
  2. 处理前k个元素：遍历前k个元素，维护队列的单调性（从大到小）。
  3. 滑动窗口：从第k个元素开始，每次移动窗口时：
    • 移除队列中不在当前窗口范围内的元素。
    • 维护队列的单调性，将新元素的索引加入队列。
    • 队列头部元素对应的数值即为当前窗口的最大值。

代码实现​

function maxSlidingWindow(nums, k) {
    const result = [];
    const deque = []; // 存储索引，保持队列头部对应的元素最大
    
    for (let i = 0; i < nums.length; i++) {
        // 移除不在当前窗口范围内的元素（队列头部）
        while (deque.length > 0 && deque[0] <= i - k) {
            deque.shift();
        }
        
        // 维护队列单调性，移除队列尾部比当前元素小的元素
        while (deque.length > 0 && nums[deque[deque.length - 1]] < nums[i]) {
            deque.pop();
        }
        
        // 将当前元素索引加入队列尾部
        deque.push(i);
        
        // 当窗口形成后，记录最大值
        if (i >= k - 1) {
            result.push(nums[deque[0]]);
        }
    }
    
    return result;
}

代码解释​

  1. 维护队列单调性：在每次添加新元素前，移除队列尾部所有比当前元素小的元素，确保队列中的元素从大到小排列。
  2. 窗口滑动处理：
    • 移除过期元素：若队列头部的索引超出当前窗口范围（即 <= i - k），则移除该元素。
    • 添加新元素：将当前元素的索引加入队列尾部，保持单调性。
  3. 记录结果：当窗口大小达到k后，每次滑动记录队列头部元素对应的数值。

复杂度分析​

  • 时间复杂度：O(n)，每个元素最多入队和出队一次。
  • 空间复杂度：O(k)，队列最多存储k个元素的索引。

示例分析​

以数组 [1, 3, -1, -3, 5, 3, 6, 7] 和 k = 3 为例：

  1. 初始窗口 [1, 3, -1]：
    • 队列状态：[1]（对应元素3）
    • 最大值：3
  2. 窗口滑动至 [3, -1, -3]：
    • 队列状态：[1, 2]（对应元素3, -1）
    • 最大值：3
  3. 窗口滑动至 [-1, -3, 5]：
    • 队列状态：[4]（对应元素5）
    • 最大值：5
  4. 窗口滑动至 [-3, 5, 3]：
    • 队列状态：[4, 5]（对应元素5, 3）
    • 最大值：5
  5. 窗口滑动至 [5, 3, 6]：
    • 队列状态：[6]（对应元素6）
    • 最大值：6
  6. 窗口滑动至 [3, 6, 7]：
    • 队列状态：[7]（对应元素7）
    • 最大值：7

最终结果：[3, 3, 5, 5, 6, 7]。

其他解法对比​

  1. 暴力法：遍历每个窗口，时间复杂度O(nk)。
  2. 优先队列（堆）：维护大小为k的最大堆，时间复杂度O(n log k)。
  3. 双端队列：本文方法，时间复杂度O(n)，最优解。

双端队列通过维护单调性，避免了重复比较，高效地解决了滑动窗口最大值问题。

双端队列​

双端队列（Deque，全称 Double-Ended Queue）是一种特殊的队列，允许在队列的两端进行元素的插入和删除操作。它结合了队列（FIFO）和栈（LIFO）的特性，既可以像队列一样从一端添加、另一端移除元素，也可以像栈一样从一端添加和移除元素。

双端队列的核心操作​

  1. 两端插入：
    • pushFront(element)：从队列头部插入元素。
    • pushBack(element)：从队列尾部插入元素。
  2. 两端删除：
    • popFront()：从队列头部移除元素。
    • popBack()：从队列尾部移除元素。
  3. 获取两端元素：
    • front()：获取队列头部元素。
    • back()：获取队列尾部元素。

为什么滑动窗口最大值问题用双端队列？​

在滑动窗口问题中，我们需要高效维护窗口内的最大值。双端队列的优势在于：

  1. 单调性维护：通过从尾部移除比当前元素小的元素，确保队列中的元素始终按从大到小排列，头部元素即为当前窗口最大值。
  2. 窗口范围控制：通过头部移除超出窗口范围的元素，确保队列只包含当前窗口内的元素。
  3. 时间复杂度最优：每个元素最多入队和出队一次，总时间复杂度为 O(n)，优于暴力法（O(nk)）和优先队列（O(n log k)）。

双端队列在滑动窗口中的具体应用（以最大值为例）​

以数组 [1, 3, -1, -3, 5, 3, 6, 7]，k=3 为例，演示双端队列的工作过程：

  1. 初始窗口 [1, 3, -1]（i=0,1,2）：

    • i=0：队列为空，插入索引0 → deque = [0]。
    • i=1：nums[1]=3 > nums[0]=1，移除索引0，插入索引1 → deque = [1]（对应元素3）。
    • i=2：nums[2]=-1 < nums[1]=3，直接插入索引2 → deque = [1, 2]。
    • 窗口形成，记录最大值 nums[1]=3。

  2. 窗口滑动至 [3, -1, -3]（i=3）：

    • 检查头部索引1是否超出窗口（i-k=3-3=0，1>0，有效）。
    • nums[3]=-3 < nums[2]=-1，插入索引3 → deque = [1, 2, 3]。
    • 记录最大值 nums[1]=3。

  3. 窗口滑动至 [-1, -3, 5]（i=4）：

    • 头部索引1超出窗口（1 ≤ 4-3=1，移除），新头部为索引2。
    • nums[4]=5 > nums[2]=-1，移除索引2、3，插入索引4 → deque = [4]（对应元素5）。
    • 记录最大值 nums[4]=5。

  4. 后续窗口类似处理，队列始终维护当前窗口内的递减序列，头部即为最大值。

双端队列 vs 其他数据结构​

方法时间复杂度空间复杂度说明
暴力法O(nk)O(1)遍历每个窗口，效率低
优先队列（堆）O(n log k)O(k)维护最大堆，但堆顶可能过期
双端队列O(n)O(k)最优解，利用单调性减少比较

代码中的双端队列实现（JavaScript）​

在 JavaScript 中，通常用数组模拟双端队列：

  • deque.push(i)：从尾部插入索引（对应 pushBack）。
  • deque.shift()：从头部移除索引（对应 popFront）。
  • deque.pop()：从尾部移除索引（对应 popBack）。

虽然 shift() 的时间复杂度为 O(n)，但由于每个元素最多入队和出队一次，整体时间复杂度仍为 O(n)（均摊复杂度）。

总结​

双端队列在滑动窗口问题中的核心思想是：通过维护单调队列，确保队列头部始终是当前窗口的极值，同时剔除过期元素。这种方法高效且直观，是解决滑动窗口极值问题的经典解法。如果需要进一步理解某一步的细节，可以结合具体示例或代码调试来加深理解。