双端队列就是允许在队列的两端进行插入和删除的队列。
体现在编码上，最常见的载体是既允许使用 pop、push 同时又允许使用 shift、unshift 的数组：

题目

题目描述：给定一个数组 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]

解决方案

双指针+遍历法

时间复杂度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.   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. }

双端队列法

维护一个递减的双端队列

  • 检查队尾元素，看是不是都满足大于等于当前元素的条件。如果是的话，直接将当前元素入队。否则，将队尾元素逐个出队、直到队尾元素大于等于当前元素为止。
  • 将当前元素入队
  • 检查队头元素，看队头元素是否已经被排除在滑动窗口的范围之外了。如果是，则将队头元素出队。
  • 判断滑动窗口的状态：看当前遍历过的元素个数是否小于 k。如果元素个数小于k，这意味着第一个滑动窗口内的元素都还没遍历完、第一个最大值还没出现，此时我们还不能动结果数组，只能继续更新队列；如果元素个数大于等于k，这意味着滑动窗口的最大值已经出现了，此时每遍历到一个新元素（也就是滑动窗口每往前走一步）都要及时地往结果数组里添加当前滑动窗口对应的最大值（最大值就是此时此刻双端队列的队头元素）
    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. };