leetcode59题:滑动窗口的最大值(用双端队列实现)

举报
小小谢先生 发表于 2022/04/16 00:39:18 2022/04/16
【摘要】 题目描述: 给定一个数组 nums 和滑动窗口的大小 k,请找出所有滑动窗口里的最大值。 示例: 输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3 输出: [3,3,5,5,6,7]  解释:    滑动窗口的位置        ...

题目描述:

给定一个数组 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

【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。