站长资源平台百度,安全证查询官网,小程序在线制作平台,wordpress获取站点链接题目
给你一个整数数组 nums#xff0c;有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回 滑动窗口中的最大值 。 提示#xff1a;
1 nums.length 10^5 -10^4 nums[i…题目
给你一个整数数组 nums有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回 滑动窗口中的最大值 。 提示
1 nums.length 10^5 -10^4 nums[i] 10 ^4 1 k nums.length
思路
如果暴力做法就是维护一个长度为k的数组没移动时先遍历该数组把最大值找出来。然后每移动一次如果右边新加入的数原最大值则更新最大值。如果左边移走的数就是最大值那么需要遍历此时移动后的数组找出最大值。这个找出最大值的过程为O(k)。移动整体窗口的过程是O(n)合起来就是O(nk)会超出时间限制。因为移动整体窗口的过程是省略不了的我们只能考虑如何将找出最大值的O(k)降为O(1)。
我们观察滑动窗口如果此时滑动窗口中只有两个下标i和j且ijnums[i]nums[j]那么只要i还在窗口内那么j也一定还在窗口内。且nums[i]一定是窗口中的最大值我们便不用再去遍历整个窗口了。如果我们以这个性质为出发点维护一个严格单调递减的下标从小到大的队列。即队列里存储的是下标但是值是严格单调递减的。那么就相当于队列里存储的是原数组第一大元素的下标原数组第二大元素的下标原数组第三大元素的下标……。
当向右滑动遍历到一个新元素now时我们
首先需要判断now是否大于队列末尾的第k大元素klast。 如果nowklast那么意味着队列的元素谁是第几大需要重新定义于是只要队列不为空我们便将now与队列末尾的元素last一个个比较如果now大于last就将last踢出队列直到遇到一个比now大的元素再将now插入到队列末尾因为那些被踢掉的last永远不可能是答案队列没有维护它们的必要。如果nowklast那么直接将now插入到队列末尾即可。 其次我们再判断向右滑动时是否会导致队首即原数组第一大元素滑出队列因为队列中存储的是在原数组的下标那么我们只需要判断这个队首元素是否i-k即可。
java代码
class Solution {public int[] maxSlidingWindow(int[] nums, int k) {int len nums.length;DequeInteger deque new LinkedList();int[] ans new int[len-k1];for(int i0;ik;i){while(!deque.isEmpty()nums[i]nums[deque.peekLast()]){deque.pollLast();}deque.offerLast(i);}ans[0]nums[deque.peekFirst()];for(int ik;ilen;i){while(!deque.isEmpty()nums[i]nums[deque.peekLast()]){deque.pollLast();}deque.offerLast(i);if(deque.peekFirst()i-k){deque.pollFirst();}ans[i-k1]nums[deque.peekFirst()];}return ans;
}
}
效率分析
28ms击败80.23%使用 Java 的用户。没必要再优化了。
