maxSlidingWindow.js

/*
给定一个数组 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 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
提示：
你可以假设 k 总是有效的，在输入数组不为空的情况下，1 ≤ k ≤ 输入数组的大小。
 */

function maxSlidingWindow(arr, k) {
  let re = [];
  let start = 0;
  let end = k;
  while (end <= arr.length) {
    let max = arr[start];
    // 找出每个滑动窗口的最大值

    for (let j = start + 1; j < end; j++) {
      max = Math.max(max, arr[j]);
    }
    re.push(max);
    start++;
    end++;
  }
  return re;
}
// 时间复杂度:对于每个滑动窗口，我们可以使用 O(k) 的时间遍历其中的每一个元素，找出其中的最大值。
// 对于长度为 n 的数组 nums 而言，窗口的数量为 n−k+1，因此该算法的时间复杂度为 O((n−(k-1))k)=O(nk)
// 空间复杂度为O(1)

/* 解法二：利用单调递减的队列来保存滑动窗口的最大值
 1.把第一个元素放入单调递减队列中，遍历之后的元素，如果比队尾元素小，则放入单调递减队列中；
   否则删除队尾元素,直到比队尾元素小，放入单调递减队列
 2.第一个滑动窗口形成，把队首元素做为第一个滑动窗口的最大元素
 3.依次遍历之后的元素，移动滑动窗口，如果比队尾元素小，则放入单调递减队列中；
   否则删除队尾元素,直到比队尾元素小，放入单调递减队列，
 4.当队首元素下标小于滑动窗口左边界时，则需要删掉队首元素
 5.每移动一次，队列的队首元素即为当前滑动窗口的最大值

为了方便判断边界，队列存放下标，不存放具体元素
 */

var maxSlidingWindow2 = function (nums, k) {
  const re = [];
  let start = 0;
  let helper = [];
  for (let i = 0; i < nums.length; i++) {
    // 遍历元素，移动滑动窗口，如果比队尾元素小，则放入单调递减队列中；
    // 否则删除队尾元素,直到比队尾元素小，放入单调递减队列
    while (helper.length && nums[i] > nums[helper[helper.length - 1]]) {
      helper.pop();
    }
    helper.push(i);
    if (i === k - 1) {
      re.push(nums[helper[0]]); //存放第一个滑动窗口的最大值
    }
    if(i >= k) {
      // 处理后面的元素
      start++;
      if (helper[0] < start) helper.shift(); //当队首元素下标小于滑动窗口左边界时，则需要删掉队首元素
      re.push(nums[helper[0]]);
    }
  }
  return re;
};
// 时间复杂度：O(n)，其中 n 是数组nums 的长度。每一个下标恰好被放入队列一次，并且最多被弹出队列一次，
// 因此时间复杂度为 O(n)。
// 空间复杂度：O(k)。使用的数据结构是双向的，因此「不断从队首弹出元素」保证了队列中最多不会有超过
// k+1 个元素，因此队列使用的空间为 O(k)。

console.log(maxSlidingWindow2([7],1));