Leetcode 上有这么一道困难题目： 滑动窗口最大值

看了大半天总算看懂了，记录一下。

题目

给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。

返回 滑动窗口中的最大值 。

示例 1：

输入：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

输入：nums = [1], k = 1 输出：[1]

方法

起初我直接想了一种很粗暴的方法，滑动窗孔每次向右移动一格，窗口长度固定，那么直接用 for 循环就可以遍历 nums 数组，每次循环中对窗口中的子数组做排序，去除最大值就可以了。时间复杂度是 O(n^2) 但是想到这个是困难题，不会这么简单，果不其然，这种排序的方式超时了。

超时的原因就是出在对窗口内数组的最大值排序，求最大值的话我想到可以直接用最大堆来快速获取。最大堆的时间复杂度为 O(log n)。但是由于不想撸一个最大堆，又不想引入三方库，加之想到这是一个困难题，我觉得会有更加精妙的方式。

我想不出来，直接看题解，发现有位兄弟用了队列的方式 双向队列解决滑动窗口最大值

看了好久明白了，这里用我的方式记录。

队列储存最大值

队列方式提升的地方还是在于对窗口内最大值的获取。

首先定义了一个队列 queue，在遍历 nums 的时候，将遍历到的值加入队列。

const queue = [];
for (let i = 0; i < nums.length; i++) {
  queue.push(nums[i]);
}

由于我们只需要拿到最大值，但是不知道那个值最大，所以要保存尽可能大的值。这里的方法是：每次拿到的当前值跟队列尾部的值做比较，如果队列尾部的值小于当前值，就从队列中删掉尾部的值，直到尾部的值大于当前值或者队列为空，然后将当前值放入队列尾部。

假设 nums 为 [3, 2, 1]，当前遍历到下标 0，nums[0] 为 3，将 3 入队列 queue，queue 现在是 [3]。下次遍历到下标 1，nums[1] 为 2，将 2 入队列。因为队列中的最大值是 3，如果 3 不在窗口内，需要将 3 移出队列，将 3 移出队列后，如果保证队列中剩余的数有最大值？就要将遍历到的、窗口内尽可能大的值放入队列。

当前队列内最大值是 3，也是窗口内的最大值，如果当前遍历到的值比 3 小，就可以作为弹出 3 后队列内最大值的候补。所以将 2 入队列，此时队列内为：[3, 2]。

然后考虑下面这种情况，加入队列内为：[3, 1]，然后当前遍历到的值为 2，将 2 入队列后会变成：[3, 1, 2]，如果此时 3 不在窗口内，需要移出队列，剩下的最大值 2，如果获取到？总不能遍历一遍队列吧，那就退化成 O(n^2) 了。此时发现，由于我们只需要窗口内的最大值，其他不是最大值的数字可以省略掉，那么在将当前值 2，加入队列尾部的时候，可以跟尾部的值做比较，如果尾部的值小于等于当前值，就说明在加入当前值后，尾部值不是最大值，可以移出。

所以在将当前值加入尾部之前，对比尾部的值，如果尾部的值小于等于当前值，移出，直到大于当前值或者空，然后加入当前值。

const queue = [];
for (let i = 0; i < nums.length; i++) {
  while (queue.length !== 0 && queue[queue.length - 1] < nums[i]) {
	  queue.pop();
	}
  queue.push(nums[i]);
}

这样的话，就能够让窗口内的最大值保持在队列头部，队列内的其他值会按照降序排列。

随着遍历的进行，如果队列头部的值不在窗口了，就将头部的值移出。为了方便判断队列的值是否在窗口内，队列可以存放下标，而不是值。

const queue = [];
for (let i = 0; i < nums.length; i++) {
  while (queue.length !== 0 && queue[queue.length - 1] < nums[i]) {
	  queue.pop();
	}
  // queue.push(nums[i]);
	queue.push(i);
	
	// i 的下标基于 0，k 基于 1，
	if (queue[0] <= i - k) {
		queue.shift();
	}
}

因为一开始有个初始化窗口的流程，在初始化窗口后，再将拿到窗口内的最大值

const res = [];
const queue = [];
for (let i = 0; i < nums.length; i++) {
  while (queue.length !== 0 && queue[queue.length - 1] < nums[i]) {
	  queue.pop();
	}
  // queue.push(nums[i]);
	queue.push(i);
	
	// i 的下标基于 0，k 基于 1，
	if (queue[0] <= i - k) {
		queue.shift();
	}
	
	if (i >= k - 1) {
		res.push(nums[queue[0]]);
	}
}

return res;

以上。