239. 滑动窗口最大值
Difficulty: 困难
给你一个整数数组 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 3
1 [3 -1 -3] 5 3 6 7 3
1 3 [-1 -3 5] 3 6 7 5
1 3 -1 [-3 5 3] 6 7 5
1 3 -1 -3 [5 3 6] 7 6
1 3 -1 -3 5 [3 6 7] 7
示例 2:
输入:nums = [1], k = 1
输出:[1]
示例 3:
输入:nums = [1,-1], k = 1
输出:[1,-1]
示例 4:
输入:nums = [9,11], k = 2
输出:[11]
示例 5:
输入:nums = [4,-2], k = 2
输出:[4]
提示:
1 <= nums.length <= 10<sup>5</sup>
-10<sup>4</sup> <= nums[i] <= 10<sup>4</sup>
1 <= k <= nums.length
题意
在一个滑动窗口内,每次滑动位置时给出当前窗口的最大值。这题和剑指Offer上的59题是一样的。
思路
使用双端队列。维护一个队列,队列中的元素是窗口中的值,且保证队列是降序排列的。当窗口右移一个位置时,先判断左移出的数值是否是双端队列的队头(队列中的最大值),如果是,说明当前窗口中的最大值移出去了,需要更新最大值,因为队列的降序的,此时新的队头就是最大值;判断完左移出的值后,判断右移进窗口的值,当新的值比队尾来得小,那么就出队,反之,将新的值入队(这样保证队列始终是降序的,出队的值是小于新值的,同时在数组中他们比新值考前,当新值没有出队时,他们不可能是最大值)。
使用优先队列。使用双端队列时,可以看到时间复杂度位O(nk),当数据量大时,效率还是很低的。从官方题解中启发,只要维护一个含有窗口中的最大值的数据结构就行--优先队列。所以,每次我们要拿取最大值时,先判断大顶堆的头部是不是在窗口内就行。
代码:
/**
*使用双端队列
*/
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
int[] res = new int[nums.length - k + 1];
LinkedList<Integer> queue = new LinkedList<>();
for(int i=0, idx=0; i<nums.length; i++){
if(i - k >= 0 && i - k == queue.peekFirst()){
queue.pollFirst();
}
while(!queue.isEmpty() && nums[i] > nums[queue.peekLast()])
queue.pollLast();
queue.offerLast(i);
res[idx] = nums[queue.peekFirst()];
idx = i - k + 1 < 0 ? 0 : idx + 1;
}
return res;
}
}
执行用时:33 ms, 在所有 Java 提交中击败了66.81%的用户
内存消耗:50.2 MB, 在所有 Java 提交中击败了70.71%的用户
/**
*使用优先级队列
*/
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
int[] res = new int[nums.length - k+1];
PriorityQueue<Node> queue = new PriorityQueue<>((a, b) -> b.val-a.val);
for(int i=0, idx = 0; i<nums.length; i++){
queue.offer(new Node(nums[i], i));
while(i-k >= 0 && queue.peek().idx <i-k+1)
queue.poll();
res[idx] = queue.peek().val;
idx = i-k+1 >= 0 ? idx + 1 : 0;
}
return res;
}
class Node{
int val;
int idx;
public Node(int val, int idx){
this.val = val;
this.idx = idx;
}
}
}
执行用时:76 ms, 在所有 Java 提交中击败了11.36%的用户
内存消耗:59.2 MB, 在所有 Java 提交中击败了8.85%的用户