题解 | #滑动窗口的最大值#

主要通过遍历所有的滑动窗口，找到每一个窗口的最大值，窗口的数量为 len(num) - size + 1

1、特殊情况：窗口大小为0或者窗口大于数组的长度，直接返回空列表

2、初始化返回列表res，遍历所有滑动窗口

3、找到窗口的最大值，存入res

4、返回res

图解：

Python版本

# -*- coding:utf-8 -*-
class Solution:
    def maxInWindows(self, num, size):
        # write code here
        # 返回数组
        res = []
        # 如果窗口的大小等于数组的长度，直接返回数组的最大值
        if size == len(num):
            return [max(num)]
        # 特殊情况
        if size == 0 or size > len(num):
            return res
        # 对数组进行遍历
        for i in range(len(num)-size+1):
            # 从数组中找到窗口大小的数组
            tmp = num[i:i+size]
            # 获取最大值存入返回数组
            res.append(max(tmp))
        return res

复杂度分析

时间复杂度：N表示数组的长度，遍历窗口时间，找到窗口内最大值时间，总时间为

空间复杂的：返回数组占用空间

算法思想二：双端队列

解题思路：

一个滑动窗口实际上可以看成一个队列。当窗口滑动时，处于窗口第一个位置的数字被删除，同时在窗口的末尾又增加了一个新的数字。这符合队列“先进先出”的特性

因此可使用双端队列，主要思想是不把所有的值都加入滑动窗口，而是只把有可能成为最大值的数加入滑动窗口，这就需要一个两边都可以操作的双向队列。

实例：

数组【2,3,4,2,6,2,5,1】为例，滑动窗口大小为3

1、先把第一个数字2加入队列，第二个数字是3，比2大，所以2不可能是最大值，所以把2删除，3存入队列。

2、第三个数是4，比3大，同样删3存4，此时滑动窗口以遍历三个数字，最大值4在队列的头部。
3、第4个数字是2，比队列中的数字4小，当4滑出去以后，2还是有可能成为最大值的，因此将2加入队列尾部，此时最大值4仍在队列的头部。

4、第五个数字是6，队列的数字4和2都比它小，所以删掉4和2，将6存入队列尾部，此时最大值6在队列头部。
5、第六个数字是2，此时队列中的数6比2大，所以2以后还有可能是最大值，所以加入队列尾部，此时最大值6在仍然队列头部。
······
依次进行，这样每次的最大值都在队列头部。
还有一点需要注意的是：如果后面的数字都比前面的小，那么加入到队列中的数可能超过窗口大小，这时需要判断滑动窗口是否包含队头的这个元素，为了进行这个检查，我们可以在队列中存储数字在数组中的下标，而不是数值，当一个数字的下标和当前出来的数字下标之差大于等于滑动窗口的大小时，这个元素就应该从队列中删除。

图解：

步骤	数组元素	窗口	队列	最大值
1	2	2	2
2	3	2，3	3
3	4	2，3，4	4	4
4	2	3，4，2	4，2	4
5	6	4，2，6	6	6
6	2	2，6，2	6，2	6
7	5	6，2，5	6，5	6
8	1	2，5，1	5，1	5

最后返回结果【4，4，6，6，6，5】

代码展示：

JAVA版本

import java.util.*;
public class Solution {
    public ArrayList<Integer> maxInWindows(int [] num, int size) {
        // 返回列表
        ArrayList<Integer> res=new ArrayList<>();
        // 特殊情况处理
        if(num==null || num.length<1 || size<=0 || size>num.length)
            return res;
        // 双端队列
        Deque<Integer> queue=new LinkedList<>();
        for(int i=0;i<num.length;i++){
            while(!queue.isEmpty() && queue.peek()<i-size+1) //超出范围的去掉
                 queue.poll();
            //当前值大于之前的值，之前的不可能是最大值，可以删掉
            while(!queue.isEmpty() && num[i]>=num[queue.getLast()]) 
                 queue.removeLast();
            // 进入队列
            queue.add(i);
            if(i>=size-1){ //此时开始是第一个滑动窗口
                res.add(num[queue.peek()]);
            }
        }
        return res;
    }
}