59-滑动窗口的最大值~Easy.md

滑动窗口的最大值

给定一个数组和滑动窗口的大小，请找出所有滑动窗口里的最大值。

例如，如果输入数组 [2,3,4,2,6,2,5,1] 及滑动窗口的大小 3，那么一共存在 6 个滑动窗口，它们的最大值分别为 [4,4,6,6,6,5]。

注意：

• 数据保证 k 大于 0，且 k 小于等于数组长度。

数据范围

• 数组长度 [1,1000]。

样例

输入：[2, 3, 4, 2, 6, 2, 5, 1] , k=3

输出: [4, 4, 6, 6, 6, 5]

思路：

1. 初始化：定义两个数组，dq用作双端队列，res用来存储结果。
2. 遍历数组：使用for循环遍历输入数组nums。
3. 维护队列：如果dq不为空，且队列头部元素的索引等于当前窗口起始位置的i - k，则将队列头部元素移除，因为这个元素不再属于当前滑动窗口。
4. 调整队列：当dq不为空，且当前元素nums[i]大于队列尾部元素的值时，移除队列尾部元素，因为队列尾部元素不是当前窗口的最大值。
5. 入队：将当前元素的索引i入队到dq。
6. 计算最大值：当i大于等于k - 1时，说明当前窗口已经包含了足够多的元素，此时队列头部元素（dq[0]）对应的值即为当前窗口的最大值，将其添加到结果数组res。
7. 返回结果：循环结束后，返回结果数组res。

因此整个算法的时间复杂度是O(n)，其中n是输入数组的长度。空间复杂度是O(k)，因为双端队列最多包含k个元素。

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number[]}
 */
var maxSlidingWindow = function (nums, k) {
  const dq: number[] = [];
  const res: number[] = [];

  for (let i = 0; i < nums.length; i++) {
    if (dq.length && dq[0] == i - k) dq.shift(); // 队头不在窗口范围内

    while (dq.length && nums[i] > nums[dq[dq.length - 1]]) {
      //待入队元素比队尾元素大
      dq.pop();
    }

    dq.push(i);
    if (i >= k - 1) res.push(nums[dq[0]]);
  }

  return res;
};