Day263:请写出以下代码结果，并解释为什么？

let { ...yideng } = Object.create({ x: 1 });
console.log(yideng.x);

每日一题会在下午四点在交流群集中讨论，五点小程序中更新答案欢迎大家在下方发表自己的优质见解

二维码加载失败可点击小程序二维码

扫描下方二维码，收藏关注，及时获取答案以及详细解析，同时可解锁800+道前端面试题。

分析

首先解释下滑动窗口的位置，比如给出的这个示例,滑动窗口的位置分别有如下情况

[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
// 所以最终会输出 [3,3,5,5,6,7]

这道题如果只是为了做对，其实是不难的，可以直接模拟上边的这个过程就可以了。

按照题意，它要求我们在遍历数组的过程中，约束一个窗口--窗口的本质实质上就是一个范围，像这样 [1 3 -1] -3] 5 3 6 7,范围被圈定在了前三个元素。

如果要约束范围，我们是不是可以想到可以利用双指针。所以这里我们可以定义一个左指针和一个右指针，分别指向窗口的两端即可。

这样处理之后，是不是我们直接把这个窗口里的数字取出来，遍历一遍，求出最大值，然后把最大值存进结果数组是不是就行了。这样第一个窗口的最大值就有了。

接着，求第二个窗口的最大值，是不是移动指针，重复上边的过程，第二个窗口的最大值也取到了。

编码实现

/**
 * 双指针 + 遍历
 * @param {number[]} nums
 * @param {number} k
 * @return {number[]}
 */
const maxSlidingWindow = function (nums, k) {
  // 定义结果数组
  const res = [];
  const len = nums.length;
  // 处理边界情况
  if (k === 0 || len === 0) return res;

  // 初始化左右指针
  let left = 0,
    right = k - 1;
  // 当数组没有遍历完成时，执行循环体内的逻辑
  while (right < len) {
    // 计算当前窗口的最大值
    const max = calMax(nums, left, right);
    // 将最大值推入结果数组
    res.push(max);
    // 左右指针前进一步
    left++;
    right++;
  }
  return res;
};

/**
 * 求数组中的最大值
 * @param {nums[]} arr
 * @param {number} left
 * @param {number} right
 * @return {number} maxNum
 */
function calMax(arr, left, right) {
  // 处理数组为空的边界情况
  if (!arr || !arr.length) {
    return;
  }
  // 初始化 maxNum 为窗口的第一个元素
  let maxNum = arr[left];
  // 遍历窗口内的所有元素，更新maxNum 的值
  for (let i = left; i <= right; i++) {
    if (arr[i] > maxNum) {
      maxNum = arr[i];
    }
  }
  // 返回最大值
  return maxNum;
}

双端队列法

上边的解法，在面试中写上去，完全没有问题。

但是可能有的同学觉得这个 calMax 这个函数多余了，认为可以直接用Math.max这个 JS 的原生方法。其实就是算是 Math.max,也不可避免的需要对你传入的多个数字做最小值查找，calMax 和 Math.max做的工作可以说是一样辛苦。上边我们是自己动手实现了一个calMax ，这样大家对查找过程的时间开销会有更直观的感知。

现在我们思考一下，上边的这一波下来，时间复杂度是多少？

这波操作里，涉及了两层循环，外层循环 while,它和滑动窗口前进的次数有关。滑动窗口前进多少次，while 就执行多少次。

假设数组的规模是 n，那么从起始位置开始，滑动窗口每走一步，一共可以走n-k次。注意不要忘记了初始位置也算做一步，因此一共走了 n-k+1 步。然后每个窗口又会固定执行 k 次遍历。注意 k 可不是一个常数，它和 n 一样也是一个变量。因此这个时间复杂度可以记为O(kn)。

O(kn) 虽然不差，但对这道题来说，还不是最好。因此在面试的过程中，如果你采用了上面这套解法做出了这个题，面试官很可能会追问你，还可以优化吗？如何进行优化？或者，直接说，你可以在线性时间复杂度内解决此问题吗？

答案当然是能。那如何将O(kn) 变为O(n) 呢？

优化思路分析

要想优化，就需要想一下如何才能丢掉这个 k。

k 之所以会产生，是因为我们现在只能通过遍历来更新最大值，有没有更高效的方法呢？

有，我们可以通过双端队列的方式。什么是双端队列呢？

双端队列就是允许在队列的两端进行插入和删除的队列。而使用双端队列的核心的思路就是维护一个有效的递减队列。

这里我们来分下这个过程。比如我们创建了一个双端队列。

接下来，我们开始遍历 nums,然后对遍历的元素进行判断是否将其推入双端队列。判断规则如下：

遍历到的元素和双端队列队尾的元素进行比较，如果对尾的元素小于当前遍历到的元素，那说明双端队列的递减趋势被打破了，这时我们就要将队尾的元素依次出队，直到队尾元素大于等于当前遍历到的元素。这时再将当前元素入队。
遍历的元素如果小于双端队列的队尾元素，直接入队。

为什么位置递减队列呢？主要是确保队头元素是当前窗口的最大值。

当遍历到第 k 个元素的时候，这时第一个窗口的最大值就出现了。就可以将最大值 push 进结果数组。继续往下遍历，每次遍历将双端队列的队头元素推入结果数组即可。

另外还要注意这个双端队列的有效性，我们要确保双端队列中只包括当前窗口内的元素。

优化编码试下

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number[]}
 */
const maxSlidingWindow = function (nums, k) {
  // 结果数组
  const res = [];
  const len = nums.length;
  // 处理边界情况
  if (k === 0 || len === 0) return res;
  // 创建双端队列
  const queue = [];
  // 遍历数组
  for (let i = 0; i < len; i++) {
    // 判断是否推入双端队列
    // 如果双端队列队尾元素小于当前遍历元素，那需要将队尾元素出栈
    while (queue.length && nums[queue[queue.length - 1]] < nums[i]) {
      // 将队尾元素(索引)不断出队，直至队尾元素大于等于当前元素
      queue.pop();
    }
    // 如果当前遍历元素大于双端队列末尾元素，入队当前元素索引
    // 注意是索引
    queue.push(i);
    // 保证双端队列有效性，只维持当前窗口的元素
    // 通过判断队头元素索引是否在窗口内，如果不在
    while (queue.length && queue[0] <= i - k) {
      // 将队头元素出队
      queue.shift();
    }
    // 如果 i > k - 1，每次都记录最大值
    if (i >= k - 1) {
      res.push(nums[queue[0]]);
    }
  }
  return res;
};

lgwebdream / FE-Interview