网站推广员是什么,wordpress 插件路径,wordpress个人中心页,京东那个做快消的网站大家好#xff0c;我是怒码少年小码。
今天这篇就讲一道题目#xff0c;不难#x1f60e;#xff0c;但是一定要学会自己思考。
滑动窗口最大值
LeetCode 239#xff1a;给你一个整数数组 nums#xff0c;有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。…大家好我是怒码少年小码。
今天这篇就讲一道题目不难但是一定要学会自己思考。
滑动窗口最大值
LeetCode 239给你一个整数数组 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 _______ 31 [3 -1 -3] 5 3 6 7 _______ 31 3 [-1 -3 5] 3 6 7 _______ 51 3 -1 [-3 5 3] 6 7 _______ 51 3 -1 -3 [5 3 6] 7 _______ 61 3 -1 -3 5 [3 6 7] _______ 7
直接比较法
首先我第一个想到的是滑动窗口直接比较的方法既然是求每次滑动窗口的最大值那就维护两个指针当两个指针每次移动的时候都求一下当前窗口内的最大值求出后放到存放最大值的数组中。这样一直到右指针到达数组的末尾。
public int[] maxSlidingWindow(int[] nums, int k) {int left 0;int right k - 1;int len nums.length- k 1 ;int[] maxList new int[len];while(right nums.length){int max nums[left];for(int i left ; i right ; i ){if(nums[i] max){max nums[i];}}maxList[left] max;left;right;}return maxList;
}当然很不幸这种方法超出了时间限制 - 。接下来讲的方法才是本篇的重点。
滑动窗口与堆
本题初始时我们将数组 nums 的前 k个元素放入优先队列中。每当我们向右移动窗口时我们就可以把一个新的元素放入优先队列中此时堆顶的元素就是堆中所有元素的最大值。然而这个最大值可能并不在滑动窗口中在这种情况下这个值在数组 nums 中的位置出现在滑动窗口左边界的左侧。因此当我们后续继续向右移动窗口时这个值就永远不可能出现在滑动窗口中了我们可以将其永久地从优先队列中移除。
我们不断地移除堆顶的元素直到其确实出现在滑动窗口中。此时堆顶元素就是滑动窗口中的最大值。为了方便判断堆顶元素与滑动窗口的位置关系我们可以在优先队列中存储二元组 (num,index)表示元素num 在数组中的下标为index。
public int[] maxSlidingWindow(int[] nums, int k) {int n nums.length;//定义优先级队列自定义排序器首先按照nums元素值进行降序排序如果元素值相等则按照数组下标值进行降序排序PriorityQueueint[] pq new PriorityQueueint[](new Comparatorint[](){public int compare(int[] pair1 , int[] pair2){return pair1[0] ! pair2[0] ? pair2[0]-pair1[0]:pair2[1]-pair1[1];}});// 前k个元素入队for(int i 0;i k ; i){pq.offer(new int[]{nums[i],i});}// 初始化结果数组int[] ans new int[n - k 1];ans[0] pq.peek()[0];// 开始滑动窗口for(int i k ; i n ; i){// 新的元素入队pq.offer(new int[]{nums[i],i});// 因为已经排好序因此可以通过peek剔除掉当前队列中为最大值但非窗口中的的元素循环结束后则队首元素为当前队列中为最大值且是窗口中的元素while(pq.peek()[1] i - k){pq.poll();}ans[i - k 1] pq.peek()[0];}return ans;
}首先我们有一个整数数组 nums 和一个窗口大小 k。我们需要找到每个窗口中的最大值并将这些最大值存储在一个新的数组 ans 中。
代码的核心是使用优先队列PriorityQueue来维护窗口中的元素并根据它们的值和索引进行比较。
首先我们创建一个优先队列 pq并通过传入一个自定义的比较器来定义元素的比较规则。比较器中的比较规则是根据元素的值和索引进行比较如果元素的值不相等则按值的降序排列如果元素的值相等则按索引的降序排列。
接下来我们遍历数组 nums 的前 k 个元素并将它们添加到优先队列 pq 中。每个元素都是一个数组包含元素的值和索引。 new int[]{nums[i], i} 是一个匿名整数数组对象的创建和初始化。它的作用是创建一个包含两个元素的整数数组并将 nums[i] 赋值给数组的第一个元素将 i 赋值给数组的第二个元素。 在这个特定的代码中我们使用 new int[]{nums[i], i} 来创建一个包含当前元素值 nums[i] 和当前索引 i 的整数数组。然后我们将这个数组添加到优先队列 pq 中以便在后续的操作中使用。
然后我们创建一个新的数组 ans用于存储每个窗口的最大值。我们首先将优先队列 pq 中的最大元素的值存储在 ans 的第一个位置。
接下来我们从第 k 个元素开始遍历数组 nums。对于每个元素我们将其添加到优先队列 pq 中并执行以下操作 检查优先队列 pq 的顶部元素最大元素的索引是否在当前窗口范围内。如果不在范围内说明该元素已经不在当前窗口中我们需要将其从优先队列 pq 中移除。我们反复执行此操作直到顶部元素的索引在当前窗口范围内。 将优先队列 pq 的顶部元素的值存储在 ans 数组中的相应位置。这个值就是当前窗口的最大值。
重复以上步骤直到遍历完整个数组 nums。
最后我们返回数组 ans其中包含了每个窗口的最大值。
双端队列
这种方法就当是一个小扩展
第一种方法在每个窗口内通过遍历查找最大值时间复杂度为 O(k)。可以使用双端队列Deque 来优化这个过程将当前窗口内的较小元素从队列中移除以保持队列的头部始终是窗口内的最大值的下标。这样可以将时间复杂度降低到 O(1)。
public int[] maxSlidingWindow(int[] nums, int k) {int n nums.length;if (n * k 0) return new int[0];DequeInteger deque new ArrayDeque();int[] maxList new int[n - k 1];for (int i 0; i nums.length; i) {// 移除超出窗口范围的元素if (!deque.isEmpty() deque.peek() i - k 1) {deque.poll();}// 移除窗口内小于当前元素的元素保持队列头部始终是最大值while (!deque.isEmpty() nums[deque.peekLast()] nums[i]) {deque.pollLast();}//队列中加入数组的下标deque.offer(i);// 将窗口内的最大值存储在结果数组中if (i - k 1 0) {maxList[i - k 1] nums[deque.peek()];}}return maxList;
}小码补充
防止有人不了解Java中的双端队列这里我们做一个简单的知识补充
在Java中Deque 接口是双端队列Double Ended Queue的一种实现。Deque 具有队列和栈的性质可以在队列的两端进行插入和删除操作。下面逐一解释 Deque 接口中的四个方法poll()、peek()、peekLast() 和 offer()。
poll() 方法用于检索并删除队列的头元素首部元素。如果队列为空poll() 方法将返回 null。peek() 方法用于检索队列的头元素首部元素但不删除它。如果队列为空peek() 方法将返回 null。peekLast() 方法用于检索队列的尾元素尾部元素但不删除它。如果队列为空peekLast() 方法将返回 null。offer() 方法用于在队列的尾部插入一个元素。如果队列已满则 offer() 方法将返回 false否则返回 true。
下面是这些方法的示例用法
import java.util.*;
public class DequeExample {public static void main(String[] args) {DequeInteger deque new ArrayDeque();// 添加元素到队列尾部deque.offer(1);deque.offer(2);deque.offer(3);System.out.println(deque); // 输出: [1, 2, 3]// 检索并删除队列头部元素int first deque.poll();System.out.println(first); // 输出: 1System.out.println(deque); // 输出: [2, 3]// 检索队列头部元素但不删除int peeked deque.peek();System.out.println(peeked); // 输出: 2// 检索队列尾部元素但不删除int peekedLast deque.peekLast();System.out.println(peekedLast); // 输出: 3}
}总结Deque 接口中的 poll()、peek()、peekLast() 和 offer() 方法分别用于检索和操作双端队列的元素。poll() 方法从队列头部检索并删除元素peek() 方法从队列头部检索元素但不删除peekLast() 方法从队列尾部检索元素但不删除offer() 方法将元素插入到队列尾部。 END
说实话还是很有难度的那个滑动窗口和堆的配合我也是想了半天才搞懂不就是力扣上的难度题目我没事 - 。
