蓝桥杯入门即劝退（二十五）滑动窗口最大值（双向队列）

ゞ浴缸里的玫瑰 2023-09-24 22:10 35阅读 0赞

**欢迎===关注===点赞===评论，共同学习，共同进步！**

**------持续更新蓝桥杯入门系列算法实例--------**

**如果你也喜欢Java和算法，欢迎订阅专栏共同学习交流！**

**你的点赞、关注、评论、是我创作的动力！**

**-------希望我的文章对你有所帮助--------**

> **[ 专栏：蓝桥杯系列][Link 1]**

## 一、题目描述 ##

给你一个整数数组 `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]

## 二、解题思路 ##

> **1、本题是滑动窗口的典型题目，但是常规的思路会使得时间复杂度比较大从而超时，因此采用双向队列ArrayDeque来优化算法。**
> 
> **2、首先将窗口看成是容量为k的一个容器，其中左边是头部，且要保证它是最大的，否则将逐步清空队列以保证队头是最大的。**
> 
> **3、首先将数组元素放入容器中，且第进一个元素只能是数组中恰好位于容器底部的位置，如**
> 
> **k=3,num=\{3,4,7,9,4,8\}，只能把7作为队头元素。**
> 
> **4、最后将符合条件的窗口内的最大值保存返回即可。**
> 
> **5、记录的是数组中的下标。**

## 三、实现代码 ##

>     public int[] maxSlidingWindow(int[] nums, int k) {//滑动窗口最大值
>             ArrayDeque <Integer>queue=new ArrayDeque<>();
>             int L=nums.length;
>             int index=0;//数组下标
>             if (L==1)  return nums;
>             int res[]=new int[L-k+1];//结果个数为L-k+1个
>             for (int i=0;i<L;i++)
>             {
>              while (!queue.isEmpty()&&queue.peek()<i-k+1)//即使已经进入队列但是不能作为队头即移出
>              queue.poll();
>              while (!queue.isEmpty()&&nums[queue.peekLast()]<nums[i])//后续元素有大于队头即把容器全部清空
>              queue.pollLast();
>                 queue.offer(i);//逐步放入容器
>                 if (i>=k-1)
>                 {
>                     res[index++]=nums[queue.peek()];//记录每次窗口移动最大的元素
>                 }
>             }
>     
>             return res;
>         }

> **发文不易，恳请大佬们高抬贵手！**
> 
>   
> **点赞：随手点赞是种美德，是大佬们对于本人创作的认可！**
> 
>   
> **评论：往来无白丁，是你我交流的的开始！**
> 
>   
> **收藏：愿君多采撷，是大佬们对在下的赞赏！**

[Link 1]: https://blog.csdn.net/m0_55278347/category_12083449.html?spm=1001.2014.3001.5482