今天来看下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;
写在最后
这些方法里面效率最高的是最后这种双数组的方法，但是实际场景感觉不太好用，这个题的考察点还是堆和双端队列。队列这种数据结构在实际开发场景中运用还是很多的。所以还是要多熟悉下。
