滑动窗口最大值

问题

给定一个整数数组 nums 和一个窗口大小 k，窗口从数组最左侧滑动到最右侧，每次滑动一位。返回每个窗口中的最大值。

示例：

输入：nums = [1,3,-1,-3,5,3,6,7], k = 3
输出：[3,3,5,5,6,7]

解答

暴力解法（O(n*k)）

function maxSlidingWindow(nums, k) {
  if (nums.length === 0 || k === 0) return [];
  
  const result = [];
  
  for (let i = 0; i <= nums.length - k; i++) {
    // 每个窗口都遍历找最大值
    let max = nums[i];
    for (let j = i + 1; j < i + k; j++) {
      max = Math.max(max, nums[j]);
    }
    result.push(max);
  }
  
  return result;
}

单调队列解法（O(n)）

function maxSlidingWindow(nums, k) {
  if (nums.length === 0 || k === 0) return [];
  
  const result = [];
  const deque = []; // 存储索引，保持对应值单调递减
  
  for (let i = 0; i < nums.length; i++) {
    // 移除超出窗口范围的元素
    if (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;
}

// 测试
console.log(maxSlidingWindow([1, 3, -1, -3, 5, 3, 6, 7], 3));
// 输出：[3, 3, 5, 5, 6, 7]

执行过程演示

nums = [1, 3, -1, -3, 5, 3, 6, 7], k = 3

i=0: deque=[0]           窗口未形成
i=1: deque=[1]           1<3，移除0，窗口未形成
i=2: deque=[1,2]         窗口[1,3,-1]，最大值 nums[1]=3
i=3: deque=[1,2,3]       窗口[3,-1,-3]，最大值 nums[1]=3
i=4: deque=[4]           5最大，清空队列，窗口[-1,-3,5]，最大值 5
i=5: deque=[4,5]         窗口[-3,5,3]，最大值 5
i=6: deque=[6]           6最大，清空队列，窗口[5,3,6]，最大值 6
i=7: deque=[7]           7最大，清空队列，窗口[3,6,7]，最大值 7

关键点

• 单调队列：队列中的元素保持单调递减，队首始终是当前窗口的最大值
• 存索引而非值：方便判断元素是否超出窗口范围
• 及时清理：新元素入队前，移除所有比它小的元素（它们不可能成为最大值）
• 窗口边界：当 i >= k - 1 时窗口才完整形成，开始记录结果
• 时间复杂度：每个元素最多入队出队各一次，总体 O(n)