滑动窗口求最大值 Posted on 2021-07-06 00:00:00 2021-07-06 00:00:00 by Author 摘要 给定一个数组，并且给定一个滑动框，你能找出每次框中得最大值吗？？？？？ # 滑动窗口求最大值 1. 题目描述 - 给定一个数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。返回滑动窗口中的最大值。（线性时间复杂度内解决此题, k属于合理的范围内） 2. 示例描述 - 示例一 - 输入：nums = [1,2,3,4,5,6], k = 3 - 输出：[3, 4, 5, 6] - 示例二 - 输入：nums = [1, 3, -1, -3, 5, 3, 6, 7], k = 3 - 输出：[3, 3, 5, 6, 7] 3. 解题思路 - 拿到这道题目的时候，我用的暴力解法解决了这道题（用双指针定位到滑动窗口的起始位置，然后找出这两个指针之间元素最大的值即可）。但是题目要求用线性的时间复杂度来解决。想了好久也没想出来。最后看了carl哥的题解，感觉很巧妙。他的公众号:代码随想录有详细解释，有兴趣的朋友可以去看看。下面就讲讲我看了他的题解后我自己的理解思路。 - 首先如果我们把进入滑动窗口里面的k个元素进行排列的话，这样达不到线性时间，那我们可以定义一个队列，这个队列队头记录当前滑动窗口的最大值，然后每次取队列的队头元素就可以了。有些朋友会想，直接建立一个从大到小的队列不久好了吗？这钟想法是不错的，但是会出现一个问题，就是队头元素，不在滑动窗口里面，那么本次滑动窗口里面的最大值就被覆盖了，结果就会出现错误。这样讲可能有点晦涩难懂，举个栗子:nums = [5,3,1,4,6], k = 3,首先我们队列元素分别为[5,3,1]，最大值为5，没问题，然后滑动串口移动，那么5弹出，4进入队列(队列是从队尾进入的)此时队列中[3,1,4]，那么3不是本次滑动窗口最大值，就会导致结果出错。 - 这里我们自己定义一个类，这个类中有pop方法，push方法，得到队头元素的方法，其中pop方法就是弹出即将离开滑动窗口的元素，如果该元素在队头，就可以出队。如果不在队头，说明这个元素不在队列中。(为什么只判断队头元素就可以了呢) - 这里就要看push方法了。push方法比较巧妙，即将进入窗口的值，和队列中的元素比较，比它小的元素就可以出栈了，因为比它小的元素，是比他先进入队列的，说明这些元素在它前面，那么之后这些元素也不可能成为滑动窗口里面最大的值，因为这个值比这些值大而且还排在这些值后面。所有这些值可以弹出了。这样就保证队列中保存一些比较大的值。而且这些大的值是按照所给数组排列顺序从大到小进行排列的。所以弹出元素的时候，如果队头元素不是所要弹出元素的值，那么说明该值压根没进入队列，即就是被其后面的值覆盖了。 - 具体实现细节，见如下代码，每步都要详细的注释。 4. 代码实现 ```java //定义一个自己需要的队列 class myDeque { //弹出方法，这个方法就是根据即将要滑出的元素是否在队列头部 //如果在头部，就移除这个元素。 public void pop(int value, Deque<Integer> deque) { if (!deque.isEmpty() && deque.peekFirst() == value) { deque.pop(); } } //这个push方法是这个题的精髓，这个队列中只保存相对比较大的值，如果滑动窗口将要进入的值 //比队列中所有的值都要大，那么说明这个值就是老大了，其余元素都是弟弟，都可以出队列 //如果进入的值比其中的某些值小，那么他也可以进入队列，因为队列中保存相应比较大的值 //还有一个疑问，就是队列中最大值已经不在滑动窗口里，那么你进去的时候，结果会出错。 //这里需要注意：我们在操作的时候，首先先出队列，然后在近队列，这就保证就算最大的值不在队列中，接下来 //操作的结果也不会错，因为最大的值已经出队列了啊。 public void push(int value, Deque<Integer> deque) { //如果进入的值大于队列中某些值，那么这些值都出队列 while (!deque.isEmpty() && value > deque.peekLast()) { deque.removeLast(); } //最后把进入滑动串口里的值加入到队列里 deque.addLast(value); } //这个方法是得到队列队头的元素的值 int front(Deque<Integer> deque) { return deque.peek(); } } public int[] maxSlidingWindow(int[] nums, int k) { //定义一队列， Deque<Integer> deque = new ArrayDeque<>(); //实列化一个我们自己定义的队列 myDeque my = new myDeque(); //定义一个结果集 List<Integer> result = new ArrayList<>(); //首先我们把前k个元素加入到我们自己定义的队列中(即为找到滑动窗口的位置，方便下次滑动) for (int i = 0; i < k; i++) { my.push(nums[i], deque); } //首次选出最大的值 result.add(my.front(deque)); //然后进行滑动窗口操作 for (int i = k; i < nums.length; i++) { //首先进行弹出操作，确保弹出的值，不进行本次窗口里面值的比较 my.pop(nums[i - k], deque); //然后把要进入的值加入队列中 my.push(nums[i], deque); //此时我们定义的队列中头部就是本次滑动窗口里面的最大值 //加入结果集就阔以了 result.add(my.front(deque)); } //返回数组形式的结果 int[] re = new int[result.size()]; for (int i = 0; i < re.length; i++) { re[i] = result.get(i); } //返回最后的结果 return re; } ```
{{ item.content }}
{{ child.content }}