滑动窗口最大值

给你一个整数数组 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 <= nums.length <= 105
-104 <= nums[i] <= 104
1 <= k <= nums.length
Related Topics
队列
数组
滑动窗口
单调队列
堆（优先队列）

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
import java.util.ArrayList;
import java.util.Collection;
import java.util.Deque;
import java.util.LinkedList;

//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        // 若遇到这种情况直接返回空数组
     if(k==0||nums.length==0){
         return new int[]{};

     }
        // 创建一个双端队列
        Deque<Integer>deque=new LinkedList<>();
     //结果数组的索引
     int resindex=0;
     //结果数组
     int []res=new int[nums.length-k+1];
     //遍历数组
     for(int i=0;i<nums.length;i++){
         //判断队列是否为空，并且判断队列最大元素是否过期
         if(!deque.isEmpty()&&deque.peek()==i-k){
             deque.poll();
         }
         //将所有小于最大值的元素出队列
         while(!deque.isEmpty()&&nums[deque.peekLast()]<nums[i]){
             deque.pollLast();

         }
         //添加元素
         deque.offer(i);
         //满足k时候，添加结果
         if(i>=k-1){
             res[resindex++]=nums[deque.peek()];
         }

     }
     //返回结果数组
     return res;


        
    }
}

参考视频

https://www.bilibili.com/video/BV1wb4y1h79v/?spm_id_from=333.337.search-card.all.click&vd_source=8a4c712cbbf24e41f7a5738643473ee3
真的很感谢这个up(讲的非常好,而且看评论区感觉性格超好)

leetcode代码地址

https://github.com/qingchen12331/leetcode_practice