明天来看下 LeetCode 第 239 题 - 滑动窗口最大值。
首先看下题：
给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧挪动到数组的最右侧。你只能够看到在滑动窗口内的 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 值，在数组里会有一个从 0 开始遍历到 n -k+ 1 地位的窗口，要给出每个窗口的最大值。
这题的解法有很多，咱们先来大略理下思路：
1、暴力 O(n*k)
2、堆 O(n*logk)
3、双端队列 O(n)
4、双数组（那个办法看着像这个，具体也不好形容）O(n)
都说 Talk is cheap,show me the code.，所以间接上代码。
暴力法
暴力法 代码还是比较简单的，然而有个致命的弱点是复杂度较高，间接会超时。
int[] res = new int[nums.length - k + 1];
int index = 0;
for (int i = 0; i < nums.length - k + 1; i++) {
int max = Integer.MIN_VALUE;
for (int j = i; j < i + k; j++) {max = Math.max(max, nums[j]);
}
res[index++] = max;
}
return res;堆
堆 ** 实现在各大语言里都有现成的封装类，java 外面是 PriorityQueue. 思路就是保护一个 k 大小的大顶堆，而后堆里存的是下标而不是 nums[i]，因为你能够用下标疾速找到 nums[i]，然而 nums[i]找下标会很麻烦，而后利用 index<=i- k 这个条件，将超过窗口的元素拿出去, 最初一次拿堆顶元素就是窗口最大值了。
这里实现有两种，一个是先初始化第一个窗口堆，而后循环前面，另一个是间接循环所有的，第一个适宜老手，熟了之后举荐第二种，优雅点：
/**
* 法一
*/
int n = nums.length;
PriorityQueue<Integer> pq = new PriorityQueue<>((o1, o2) -> (nums[o2] - nums[o1]));
for (int i = 0; i < k; ++i) {pq.offer(i);
}
int[] ans = new int[n - k + 1];
ans[0] = nums[pq.peek()];
for (int i = k; i < n; ++i) {pq.offer(i);
while (pq.peek() <= i - k) {pq.poll();
}
ans[i - k + 1] = nums[pq.peek()];
}
return ans;
/**
* 法二
*/
if (nums.length == 0 || k == 0) {return new int[]{};}
PriorityQueue<Integer> pq = new PriorityQueue<>((o1, o2) -> (nums[o2] - nums[o1]));
int[] ans = new int[nums.length - k + 1];
for (int i = 0; i < nums.length; ++i) {while (!pq.isEmpty() && pq.peek() <= i - k) {pq.poll();
}
pq.offer(i);
if (i - k + 1 >= 0) {ans[i - k + 1] = nums[pq.peek()];
}
}
return ans;双端队列
双端队列 ** 实现是利用 deque 能够双向出入的个性，保障 deque 外面右边元素始终最大的，这样最大元素只有每次拿 deque.peekFirst()即可。利用 deque.peekFirst() == i – k 这个调教保障超出窗口的元素进来。每次入队的时候验证 nums[i]和队尾元素大小，如果比队尾元素大，则将队尾元素取出。而后将 i 退出队列中。
/**
* 双端队列
* 工夫复杂度 O(n+k)，空间复杂度 O(n)
* 始终保持双端队列头一个元素为最大值
*/
if (nums == null || nums.length == 0) {return nums;}
int[] res = new int[nums.length - k + 1];
Deque<Integer> deque = new LinkedList<>();
for (int i = 0; i < nums.length; i++) {
// 窗口曾经占满了
if (!deque.isEmpty() && deque.peekFirst() == i - k) {// if (!deque.isEmpty() && deque.peekFirst() < i - k + 1) {deque.pollFirst();
}
// 始终保持队列按从大到小排列, 且会始终移除新加元素小的元素，如果
//nums[i]大于队列所有值，会移除队列所有值
while (!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) {deque.pollLast();
}
deque.offerLast(i);
// 当窗口满了 k 个元素，将其一个个放入 res[]数组中
if (i >= k - 1) {
// 第一个元素始终是最大的元素
res[i + 1 - k] = nums[deque.peekFirst()];
}
}
return res;双端队列 的代码其实还能够优化，下面的代码是用的零碎自带的 Deque，我后面日记外面说过零碎库函数个别会思考很多理论工业上状况和很多边界条件，因而性能不会很好，所以咱们能够进一步本人实现一个双端队列，从而进步运行工夫。
给个参考数据，我用零碎自带的 Deque，也就是下面代码，运行工夫是 39ms, 击败 50.38% 的 java 用户；而我用本人实现的 Deque，也就是上面的代码，运行工夫是 29ms, 击败了 96.29% 的 java 用户。
/**
* 数组实现双端队列
*
*/
if (nums.length == 0 || k == 0) {return new int[]{};}
int count = k + 1;
int[] deque = new int[count];
int head = 0;
int tail = 0;
int[] res = new int[nums.length - k + 1];
for (int i = 0; i < nums.length; i++) {if (tail != head && deque[head%count] == i - k) {head = (head + 1) % count;
}
while (tail != head && nums[deque[(tail - 1 + count) % count]] < nums[i]) {tail = (tail - 1 + count) % count;
}
deque[tail] = i;
tail = (tail + 1) % count;
if (i - k + 1 >= 0) {res[i - k + 1] = nums[deque[head % count]];
}
}
return res;这个数组实现的 Deque 代码其实就是后面日记的循环双端队列拿过去略微改了下，我就不做过多解释了，不太分明的能够去看看后面的设计循环双端对列的文章。
双数组
双数组办法是所有办法外面最高效的，运行工夫是 13ms，比数组的双端队列少了一半多的工夫。
然而怎么说这个办法不具普遍性，感觉有点取巧，正统办法还是双端队列优雅点。
思路是：将数组按 k 个一组分成多段，最初一段可能有余 k 个，
1、别离从右边开始找到最大值和左边开始找到最大值。
2、比拟左右最大值，大的那个就是该地位滑动窗口的最大值。
final int[] max_left = new int[nums.length];
final int[] max_right = new int[nums.length];
max_left[0] = nums[0];
max_right[nums.length - 1] = nums[nums.length - 1];
for (int i = 1; i < nums.length; i++) {max_left[i] = (i % k == 0) ? nums[i] : Math.max(max_left[i - 1], nums[i]);
final int j = nums.length - i - 1;
max_right[j] = (j % k == 0) ? nums[j] : Math.max(max_right[j + 1], nums[j]);
}
final int[] sliding_max = new int[nums.length - k + 1];
for (int i = 0, j = 0; i + k <= nums.length; i++) {sliding_max[j++] = Math.max(max_right[i], max_left[i + k - 1]);
}
return sliding_max;写在最初
这些办法外面效率最高的是最初这种双数组的办法，然而理论场景感觉不太好用，这个题的考察点还是堆和双端队列。队列这种数据结构在理论开发场景中使用还是很多的。所以还是要多相熟下。