239.滑动窗口最大值

滑动窗口最大值

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

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

示例 1：

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

示例 2：

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

提示：

• 1 <= nums.length <= $10^5$
• $-10^4$ <= nums[i] <= $10^4$
• 1 <= k <= nums.length

解析

单调递减队列：队列中存储下标，保持队列中的值从大到小。

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number[]}
 */
var maxSlidingWindow = function (nums, k) {
  const result = [];
  const deque = []; // 存储下标，单调递减

  for (let i = 0; i < nums.length; i++) {
    // 移除超出窗口范围的元素
    while (deque.length && deque[0] <= i - k) {
      deque.shift();
    }
    // 维护单调递减：移除比当前值小的元素
    while (deque.length && nums[deque[deque.length - 1]] <= nums[i]) {
      deque.pop();
    }
    deque.push(i);
    // 窗口形成后开始记录结果
    if (i >= k - 1) {
      result.push(nums[deque[0]]);
    }
  }
  return result;
};

单调队列保证队首始终是窗口内的最大值。时间复杂度 O(n)，每个元素最多入队出队各一次。