239. Sliding Window Maximum

使用一个双向队列储存当前窗口的最大值候选者,最大值放在队首

const maxSlidingWindow = function (nums, k) {
  const doubleQueue = [],
    res = [];
  for (let i = 0, ii = nums.length; i < ii; ++i) {
    // 如果当前队首的值已经不在滑动窗口了,移除它
    if (doubleQueue.length !== 0 && doubleQueue[0] < i - k + 1) {
      doubleQueue.shift();
    }
    // 当滑动窗口右移的时候,要将当前i放到队列中,把队列中小于nums[i]的都删掉(从后向前找)
    while (doubleQueue.length !== 0 && nums[doubleQueue[doubleQueue.length - 1]] < nums[i]) {
      doubleQueue.pop();
    }
    doubleQueue.push(i);
    if (i >= k - 1) {
      res[i - k + 1] = nums[doubleQueue[0]];
    }
  }
  return res;
};