一、题目内容 困难

给你一个整数数组 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]

提示：

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

    二、解题思路

    我们目的是要找出滑动窗口，每次窗口中的最大值。
    按照我们正常的思路，每次窗口变化后，我们遍历窗口，找出其中最大值，不就可以了。对！
    但这是最暴力的算法，时间复杂度为 O(n x k)，空间复杂度为O(k)。
    看看 提示 中那些数多大，就知道会超时，我们需要找其他方法。

我们维护这个窗口，每次都是从头进，从尾出。这就是一个队列数据结构，那么我们把这个窗口最大值，放在队列最前面，行不行？
仔细想想不行，下一次从尾部出去的值，我们需要花时间找到它的位置，删除它。
还需要把新添加进来的值，排序后，插入这个数，还是需要花时间。时间复杂度没有降下来。

也许我们给队列，添加一些特点，让他变得时间复杂度更低。提前说明：单调队列。

那我们想想，我们是想每次窗口移动后，找到最大值。

  1. 添加新值时：那如果 添加进队列的新值 比 队列前面的值 都大，而且 队列前面的值，在以后窗口移动时，都会被删除掉。那么他们是不是就没有留下了的必要，直接先把我们移出队列，不影响我们这一次窗口变化后的最大值，以后也不会影响。
  2. 删除旧值时：按照我们上面的操作，队列中，队头是最大是数，队尾是最小是数，呈单调递减规律。我们现在要删除的值，要不就是队头最大的数，要不就是添加新值的时候，已经被删除了。所以我们只需要比对，队头是不是我们要删除的旧值，是，则删除掉即可。

    三、具体代码

    1. class deQueue {
    2. constructor() {
    3.  this.queue = []; // 单调队列，队列头是最大的数，队列尾是最小的数
    4. }
    5. // 窗口移动时，添加进来的新值
    6. push(value) {
    7.  // 如果进来的数，比前面的数大，它是最大值，在未来窗口移动过程中，最慢被舍弃掉。
    8.  // 这意味着，前面的数，现在被舍弃掉，不影响最大值。
    9.  while (this.queue.length && value > this.queue[this.queue.length - 1]) {
    10.    this.queue.pop();
    11.  }
    12.  this.queue.push(value);
    13. }
    14. // 窗口移动时，删除的旧值
    15. delete(value) {
    16.  if (this.queue.length && value === this.queue[0]) {
    17.    this.queue.shift();
    18.  }
    19. }
    20. getLargest() {
    21.  return this.queue[0];
    22. }
    23. }
    24. /**
    25. * @param {number[]} nums
    26. * @param {number} k
    27. * @return {number[]}
    28. */
    29. var maxSlidingWindow = function (nums, k) {
    30. const queue = new deQueue();
    31. const res = [];
    32. for (let i = 0; i < k; i++) {
    33.  queue.push(nums[i]);
    34. }
    35. res.push(queue.getLargest());
    36. for (let i = k; i < nums.length; i++) {
    37.  queue.push(nums[i]);
    38.  queue.delete(nums[i - k]);
    39.  res.push(queue.getLargest());
    40. }
    41. return res;
    42. };
    43. /**
    44. * 时间复杂度：O(n)
    45. * 空间复杂度：O(k)
    46. */

    四、其他解法