leetcode59题:滑动窗口的最大值(用双端队列实现)
题目描述:
给定一个数组 nums 和滑动窗口的大小 k,请找出所有滑动窗口里的最大值。
示例:
输入: 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
思路分析:
考虑到这道题的数组要求可以头部进去、删除,尾部进去,删除,所以使用双端队列Deque。使用双端队列的单调双端队列LinkedList实现。
所谓的单调
,就是我们人为规定从队列的头部到尾部,所存储的元素是依次递减(或依次递增)的。
也就是说,我们维护一个单调的双向队列,窗口在每次滑动的时候,我就从队列头部取当前窗口中的最大值,每次窗口新进来一个元素的时候,我就将它与队列中的元素进行大小比较:
如果刚刚进来的元素比队列的尾部元素大,那么先将队列尾部的元素弹出,然后把刚刚进来的元素添到队列的尾部;
如果刚刚进来的元素比队列的尾部元素小,那么把刚刚进来的元素直接添到队列的尾部即可。
因此,通过这种既能从头部进出,又能从尾部进出的结构,来维持窗口的最大值的。
java代码:
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
Deque<Integer> deque=new LinkedList<>();
int len=nums.length;
if(len==0 ||k==0 ){
return new int[0] ;
}
int[] res=new int[len-k+1];
for(int i=0;i<k;i++){
while(!deque.isEmpty() && nums[i]>deque.peekLast()){
deque.removeLast(); //比队列元素大就弹出队尾数据
}
deque.addLast(nums[i]);//不走循环直接加到队列末尾
}
res[0]=deque.peekFirst();
for(int i=k;i<len;i++){
// 如果滑动窗口已经略过了队列中头部的元素,则将头部元素弹出
if(deque.peekFirst() == nums[i - k]){
deque.removeFirst();//
}
while(!deque.isEmpty() && deque.peekLast() < nums[i]){
deque.removeLast();
}
deque.addLast(nums[i]);
res[i - k + 1] = deque.peekFirst();
}
return res;
}
}
文章来源: blog.csdn.net,作者:小小谢先生,版权归原作者所有,如需转载,请联系作者。
原文链接:blog.csdn.net/xiewenrui1996/article/details/112883318
- 点赞
- 收藏
- 关注作者
评论(0)