seo网站推广公司,韩国网站设计欣赏,网络营销第二版课后答案,佛山有哪几个区作者 | 王磊来源 | Java中文社群#xff08;ID#xff1a;javacn666#xff09;转载请联系授权#xff08;微信ID#xff1a;GG_Stone#xff09;本文已收录至 Github《小白学算法》系列#xff1a;https://github.com/vipstone/algorithm这是一道比较基础的算法题… 作者 | 王磊来源 | Java中文社群IDjavacn666转载请联系授权微信IDGG_Stone本文已收录至 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 ≤ 输入数组的大小。LeetCodehttps://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];// 优先队列PriorityQueueInteger queue new PriorityQueue(res.length, new ComparatorInteger() {Overridepublic 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];// 存储的数据为元素的下标ArrayDequeInteger 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中的5大队列23张图万字详解「链表」从小白到大佬队列实现栈的3种方法全都击败了100%的用户关注我每天陪你进步一点点
