- max of sliding window 解题报告
这道题算经典了,因为很多笔试或者OA都会考到相关类型的题目。
这道题就给你两个input, 一个数组,一个window size k (intput:int[] nums, int k)
要输出的值就是每个window里面最大值组成的数组。
那么首先要想到的就是先建立一个返回的数组,这个数组的大小应该是nums.length - k + 1
int[] res = new int[nums.length - k + 1];
用什么算法?
这道题实际上就是sliding window的一道题,sliding window本身就是一种解决问题的形式。不过这道题有一个很好地优化空间,你不必像sliding window本身那样每次把数组中的k个数取出来,然后存最大值,因为这样会导致时间复杂度变为O(NK),而利口上面正好有一个很大的test case,所以会超时。
这道题能够节省时间复杂度的方式使用Deque,因为你可以在滑动窗口的时候直接把超出窗口空间的数字剔除,并且对比最后一个数字和即将放入队列的数字,如果比即将要进入队列的数字要小,那么就把最后一个数字去掉,这样deque里面第一个数就是当前最大的数。
而怎么保证你滑动窗口把超出窗口大小的数去掉?用deque来存index*
这是很重要的一步,因为如果你存的是数字,那就没法判断当前第一个数是否是超出窗口大小的index了。
一个比较重要的地方是deque在Java里面是通过ArrayDeque来实现的。
下面是代码
public int[] maxSlidingWindow(int[] nums, int k) {
if (nums == null) {
return new int[0];
}
int[] res = new int[nums.length - k + 1];
Deque<Integer> dq = new ArrayDeque<>();
for (int i = 0; i < nums.length; i++) {
if (!dq.isEmpty() && dq.peek() < i - k + 1) {
dq.pollFirst();
}
while (!dq.isEmpty() && nums[dq.peekLast()] < nums[i]) {
dq.pollLast();
}
dq.offer(i);
if (i >= k-1) {
res[i-k+1] = nums[dq.peek()];
}
}
return res;
}
时空复杂度
O(N)要走n次
O(K)deque的大小最大可能就是k,所以空间复杂度是k
网友评论