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

题目描述

给定一个数组和滑动窗口的大小，找出所有滑动窗口里数值的最大值。
例如，如果输入数组{2,3,4,2,6,2,5,1}及滑动窗口的大小3，那么一共存在6个滑动窗口，他们的最大值分别为{4,4,6,6,6,5}；
针对数组{2,3,4,2,6,2,5,1}的滑动窗口有以下6个： {[2,3,4],2,6,2,5,1}， {2,[3,4,2],6,2,5,1}， {2,3,[4,2,6],2,5,1}， {2,3,4,[2,6,2],5,1}， {2,3,4,2,[6,2,5],1}， {2,3,4,2,6,[2,5,1]}。
窗口大于数组长度的时候，返回空。
示例1
输入：[2,3,4,2,6,2,5,1],3
返回值：[4,4,6,6,6,5]

题目分析

对于滑动窗口来说，使用双指针的基本模板如下：

while(right<length){
   while(窗口的长度<size){
        right++; // 增加窗口长度
       // 处理窗口内的数据
   }
   left++; // 移动左边界指针
}

此处窗口数据的处理为获取最大值，可以直接暴力法遍历窗口内的所有数据，取最大值；
也可以构建单调递减的队列，每次移动左右指针时，更新队列中的数据，每个区间的最大值即为队列的头部数据。

解题思路

方法1：暴力法遍历区间最大值
根据区间长度size，可以确定数组中的每个区间（左边界和有边界），然后遍历这个区间内的所有数据，可以获取窗口的最大值。

// 确定区间的左边界
for(int i=0;i<nums.length-size;i++){
    int max;
    // 从左边界到右边界内的数据获取最大值
    for(int j=0;j<size;j++){
       max = Math.max(max, nums[i+j]);
    }
}

方法2：使用单调双向队列
暴力法需要重复遍历很多数据，效率不高，可以使用单调递减队列来存储遍历的数据，每次更新区间时，只要获取单调队列的头部数据即可；
主要思路：
1.创建单调递减队列，遍历区间内的数据；
2.如果后面的数据大于队列队尾的数据（区间最小值），需要将队列前面的数据出队列，保证队列的单调性；
3.如果后面的数据小于队列队尾数据，则直接入队列；
4.最关键的在于移动左下标时，需要将队列中的相应数据出队列（看下标小于左下标的要移除队列头）；
5.基于上述情况，需要记录数组的下标，则可以直接在队列中存储下标，排序时使用下标对应的数字，同时考虑到队列同时需要从头部删除数据和从尾部删除数据，使用双向队列；
图片说明

代码实现

方法1：暴力法遍历区间最大值

    public ArrayList<Integer> maxInWindows(int [] num, int size){
        ArrayList<Integer> result = new ArrayList<Integer>();
        if(size==0 || size>num.length) return result;
        // 遍历数组的所有区间
        for(int i=0;i<=num.length-size;i++){
            int max = num[i];
            // 获取区间中的最大值
            for(int j=1;j<size;j++){
                if(max<num[i+j]){
                    max = num[i+j];
                }
            }
            result.add(max);
        }
        return result;
    }

时间复杂度： $O(nk)$ ，n是数组长度，k是区间长度，暴力遍历次数 nk；
空间复杂度： $O(1)$ ，需要使用常量个数的变量来遍历数组和保存数据；

方法2：使用单调双向队列

    public ArrayList<Integer> maxInWindows(int [] num, int size) {
        ArrayList<Integer> res = new ArrayList<>();
        if(num == null || num.length == 0 || size == 0 || num.length < size) return res;
        int left = 0;
        int right = left+1;
        // 单调递减双向队列
        Deque<Integer> deque = new LinkedList<Integer>();
        deque.offerLast(0);
        while(right < num.length){
            while((right-left)<size){
                while(!deque.isEmpty() && num[right]>num[deque.peekLast()]){
                    // 若是后面的数比前面的大，则不需要存储前面的数
                    deque.pollLast();
                }
                // 直到遇到比后面的数大的，将后面的数加入栈中
                deque.offerLast(right);
                right++;
            }
            res.add(num[deque.peekFirst()]);
            left++;
            // 移动左下标，同时更新队列头部
            while(!deque.isEmpty() && deque.peekFirst() < left){
                deque.pollFirst();
            }
        }
        return res;
    }

时间复杂度： $O(n)$ ，指针right移动的距离为数组的长度-size，时间复杂度为n；
空间复杂度： $O(k)$ ，单调队列中最多需要使用k的空间来存储区间数据。