本文已收录至 Github《小白学算法》系列：https://github.com/vipstone/algorithm
这是一道比拟根底的算法题，波及到的数据结构也是咱们之前讲过的，我这里先买一个关子。这道面试题最近半年在亚马逊的面试中呈现过 28 次，在字节跳动中呈现过 7 次，数据来源于 LeetCode。
咱们先来看题目的形容。
题目形容
给定一个数组 nums 和滑动窗口的大小 k，请找出所有滑动窗口里的最大值。
示例:
输出: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3
输入: [3,3,5,5,6,7]
提醒：
你能够假如 k 总是无效的，在输出数组不为空的状况下，1 ≤ k ≤ 输出数组的大小。
LeetCode：https://leetcode-cn.com/problems/hua-dong-chuang-kou-de-zui-da-zhi-lcof/
题目解析
下面的题目看不懂？没关系，接下来来看这幅图能够分明的形容这道题：
从上述图片能够看出，题目的意思为：给定一个数组，每次查问 3 个元素中的最大值，数量 3 为滑动窗口的大小，之后顺次向后挪动查问相邻 3 个元素的最大值。图片中的原始数组为 [1,3,-1,-3,5,3,6,7]，最终滑动窗口的最大值为 [3,3,5,5,6,7]。
看到这个题之后，咱们的第一直觉就是暴力解法，用两层循环顺次查问滑动窗口的最大值，实现代码如下。
实现办法 1：暴力解法
暴力解法的实现思路和实现代码很直观，如下所示：
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
// 非空判断
if (nums == null || k <= 0) return new int[0];
// 最终后果数组
int[] res = new int[nums.length - k + 1];
for (int i = 0; i < res.length; i++) {
// 初始化最大值
int max = nums[i];
// 循环 k-1 次找最大值
for (int j = i + 1; j < (i + k); j++) {
max = (nums[j] > max) ? nums[j] : max;
}
res[i] = max;
}
return res;
}
}把以上代码提交至 LeetCode，执行后果如下：
从上述后果能够看出，尽管代码通过了测试，但执行效率却很低，这种代码是不能利用于生产环境中的，因而咱们须要持续找寻新的解决方案。
实现办法 2：改良版
接下来咱们略微优化一下下面的办法，其实咱们并不需要每次都通过两层循环，咱们只须要一层循环拿到滑动窗口的最大值（之前循环元素的最大值），而后在移除元素时，判断以后要移除的元素是否为滑动窗口的最大值，如果是，则进行第二层循环来找到新的滑动窗口的最大值，否则只须要将最大值和新增的元素比拟大小即可，实现代码如下：
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
// 非空判断
if (nums == null || k <= 0) return new int[0];
// 最终后果数组
int[] res = new int[nums.length - k + 1];
// 上一轮循环移除的值
int r = -Integer.MAX_VALUE;
// 滑动窗口最大值（初始化）
int max = r;
for (int i = 0; i < res.length; i++) {
// 1.判断移除的值，是否为滑动窗口的最大值
if (r == max) {
// 2.移除的是滑动窗口的最大值，循环找到新的滑动窗口的最大值
max = nums[i]; // 初始化最大值
// 循环找最大值
for (int j = i + 1; j < (i + k); j++) {
max = Math.max(max, nums[j]);
}
} else {
// 3.只须要用滑动窗口的最大值和新增值比拟即可
max = Math.max(max, nums[i + k - 1]);
}
// 最终的返回数组记录
res[i] = max;
// 记录下轮要移除的元素
r = nums[i];
}
return res;
}
}把以上代码提交至 LeetCode，执行后果如下：
从上述后果能够看出，革新之后的性能根本曾经合乎我的要求了，那文章结尾说过这道题还能够应用咱们之前学过的数据结构？那它说的是什么数据结构呢？
其实咱们能够应用「队列」来实现这道题目，它的实现思路也非常简单，甚至比暴力解法更加不便，接下来咱们持续往下看。
实现办法 3：优先队列
这个题的另一种经典的解法，就是应用最大堆的形式来解决，最大堆的构造如下所示：
最大堆的个性是堆顶是整个堆中最大的元素。
咱们能够将滑动窗口的值放入最大堆中，这样利用此数据结构的特点（它会将最大值放到堆顶），因而咱们就能够间接获取到滑动窗口的最大值了，实现代码如下：
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
// 非空判断
if (nums == null || k <= 0) return new int[]{};
// 最终后果数组
int[] res = new int[nums.length - k + 1];
// 优先队列
PriorityQueue<Integer> queue = new PriorityQueue(res.length, new Comparator<Integer>() {
@Override
public int compare(Integer i1, Integer i2) {
// 倒序排列（从大到小，默认是从小到大）
return i2 - i1;
}
});
// 第一轮元素增加
for (int i = 0; i < k; i++) {
queue.offer(nums[i]);
}
res[0] = queue.peek();
int last = nums[0]; // 每轮要移除的元素
for (int i = k; i < nums.length; i++) {
// 移除滑动窗口之外的元素
queue.remove(last);
// 增加新元素
queue.offer(nums[i]);
// 存入最大值
res[i - k + 1] = queue.peek();
// 记录每轮要移除的元素（滑动窗口最右边的元素）
last = nums[i - k + 1];
}
return res;
}
}代码解读
从上述代码能够看出：最大堆在 Java 中对应的数据结构就是优先级队列 PriorityQueue，但优先级队列默认的排序规定是从小到大进行排序的，因而咱们须要创立一个 Comparator 来扭转一下排序的规定（从大到小进行排序），之后将滑动窗口的所有元素放入到优先级队列中，这样咱们就能够间接应用 queue.peek() 拿到滑动窗口的最大值了，而后再循环将滑动窗口的边缘值移除掉，从而解决了本道题目。
把以上代码提交至 LeetCode，执行后果如下：
PS：从下面的执行后果能够看出，应用优先队列的执行效率很低，这是因为每次插入和删除都须要从新保护最大堆的元素程序，因而整个执行的效率就会很低。
实现办法 4：双端队列
除了优先队列之外，咱们还能够应用双端队列来查问滑动窗口的最大值，它的实现思路和最大堆的实现思路很像，但并不需要每次在增加和删除时进行元素地位的保护，因而它的执行效率会很高。
双端队列实现思路的外围是将滑动窗口的最大值始终放在队首地位（也就是队列的最右边），将小于最大值并在最大值右边（队首方向）的所有元素删除。这个也很好了解，因为这些绝对较小的值既没有最大值大，又在最大值的后面，也就是它们的生命周期比最大值还短，因而咱们能够间接将这些绝对较小的元素进行删除，如下图所示：
像以上这种状况下，咱们就能够将元素 1 和元素 2 删掉。
双端队列实现查问滑动窗口最大值的流程分为以下 4 步：
- 移除最右边小于最大值的元素（保障滑动窗口的最大值在队首地位）；
- 从队尾向前顺次移除小于以后要退出到队列元素的值（淘汰小值且生命周期短的元素）；
- 将新元素退出到队列开端；
- 将最大值退出到最终后果的数组中。
实现代码如下：
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
// 非空判断
if (nums == null || k <= 0) return new int[0];
// 最终后果数组
int[] res = new int[nums.length - k + 1];
// 存储的数据为元素的下标
ArrayDeque<Integer> deque = new ArrayDeque();
for (int i = 0; i < nums.length; i++) {
// 1.移除右边超过滑动窗口的下标
if (i >= k && (i - k) >= deque.peek()) deque.removeFirst();
// 2.从最初面开始移除小于 nums[i] 的元素
while (!deque.isEmpty() && nums[deque.peekLast()] < nums[i])
deque.removeLast();
// 3.下标退出队列
deque.offer(i);
// 4.将最大值退出数组
int rindex = i - k + 1;
if (rindex >= 0) {
res[rindex] = nums[deque.peek()];
}
}
return res;
}
}把以上代码提交至 LeetCode，执行后果如下：
从上述后果能够看出，双端队列相比于优先级队列来说，因为无需从新计算并保护元素的地位，所以执行效率还是挺高的。
总结
本文咱们通过 4 种形式实现了查找滑动窗口最大值的性能，其中暴力解法通过两层循环来实现此性能，代码最简略但执行效率不高，而通过最大堆也就是优先队列的形式来实现（本题）尽管比拟省事，但执行效率不高。因而咱们能够抉择应用双端队列或改良版的代码来实现查问滑动窗口的最大值。
关注公众号「Java中文社群」查看更多算法图解文章。
发表回复