认识双端队列

双端队列衍生出的滑动窗口问题，是一个经久不衰的命题热点。关于双端队列，各种各样的解释五花八门，这里大家不要纠结，就记住一句话：
双端队列就是允许在队列的两端进行插入和删除的队列。
体现在编码上，最常见的载体是既允许使用 pop、push 同时又允许使用 shift、unshift 的数组：

  1. const queue = [1,2,3,4] // 定义一个双端队列   
  2. queue.push(1) // 双端队列尾部入队 
  3. queue.pop() // 双端队列尾部出队   
  4. queue.shift() // 双端队列头部出队 
  5. queue.unshift(1) // 双端队列头部入队

现在相信你对双端队列已经形成了一个感性的认知，咱们紧接着就开始做题，在题里去认知这种结构的特征和效用。

滑动窗口问题

题目描述：给定一个数组 nums 和滑动窗口的大小 k，请找出所有滑动窗口里的最大值。

示例: 输入: 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 1 [3 -1 -3] 5 3 6 7 1 3 [-1 -3 5] 3 6 7

1 3 -1 [-3 5 3] 6 7

1 3 -1 -3 [5 3 6] 7

1 3 -1 -3 5 [3 6 7]

最大值分别对应：

3 3 5 5 6 7

提示：你可以假设 k 总是有效的，在输入数组不为空的情况下，1 ≤ k ≤ 输入数组的大小。

思路：双指针+遍历
定义一个left 左指针、定义一个 right 右指针，分别指向窗口的两端即可

  1. /**
  2.  * @param {number[]} nums
  3.  * @param {number} k
  4.  * @return {number[]}
  5.  */
  6. const maxSlidingWindow = function (nums, k) {
  7.   // 缓存数组的长度
  8.   const len = nums.length;
  9.   // 定义结果数组
  10.   const res = [];
  11.   // 初始化左指针
  12.   let left = 0;
  13.   // 初始化右指针
  14.   let right = k - 1;
  15.   // 当数组没有被遍历完时，执行循环体内的逻辑
  16.   while (right < len) {
  17.     // 计算当前窗口内的最大值
  18.     const max = calMax(nums, left, right);
  19.     // 将最大值推入结果数组
  20.     res.push(max);
  21.     // 左指针前进一步
  22.     left++;
  23.     // 右指针前进一步
  24.     right++;
  25.   }
  26.   // 返回结果数组
  27.   return res;
  28. };
  30. // 这个函数用来计算最大值
  31. function calMax(arr, left, right) {
  32.   // 处理数组为空的边界情况
  33.   if (!arr || !arr.length) {
  34.     return;
  35.   }
  36.   // 初始化 maxNum 的值为窗口内第一个元素
  37.   let maxNum = arr[left];
  38.   // 遍历窗口内所有元素，更新 maxNum 的值
  39.   for (let i = left; i <= right; i++) {
  40.     if (arr[i] > maxNum) {
  41.       maxNum = arr[i];
  42.     }
  43.   }
  44.   // 返回最大值
  45.   return maxNum;
  46. }

时间复杂度 o(kn)

可进一步优化 时间复杂度

双端队列法

使用双端队列法，核心的思路是维护一个有效的递减队列。

  1. /**
  2.  * @param {number[]} nums
  3.  * @param {number} k
  4.  * @return {number[]}
  5.  */
  6. const maxSlidingWindow = function (nums, k) {
  7.   // 缓存数组的长度
  8.   const len = nums.length;
  9.   // 初始化结果数组
  10.   const res = [];
  11.   // 初始化双端队列
  12.   const deque = [];
  13.   // 开始遍历数组
  14.   for (let i = 0; i < len; i++) {
  15.     // 当队尾元素小于当前元素时
  16.     while (deque.length && nums[deque[deque.length - 1]] < nums[i]) {
  17.       // 将队尾元素（索引）不断出队，直至队尾元素大于等于当前元素
  18.       deque.pop();
  19.     }
  20.     // 入队当前元素索引（注意是索引）
  21.     deque.push(i);
  22.     // 当队头元素的索引已经被排除在滑动窗口之外时
  23.     while (deque.length && deque[0] <= i - k) {
  24.       // 将队头元素索引出队
  25.       deque.shift();
  26.     }
  27.     // 判断滑动窗口的状态，只有在被遍历的元素个数大于 k 的时候，才更新结果数组
  28.     if (i >= k - 1) {
  29.       res.push(nums[deque[0]]);
  30.     }
  31.   }
  32.   // 返回结果数组
  33.   return res;
  34. };