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

描述

给定一个数组和滑动窗口的大小，找出所有滑动窗口里数值的最大值。窗口大于数组长度的时候，返回空

解题思路

题目描述非常清晰直白,就是一个数组,每次选择 *几个数 * ,找到这几个数中的最大值,然后向后挪动.画个图更清晰的说明题意.

方案一:暴力法

思路:

使用双端队列来做,每次保证队列长度为窗口大小,在一个窗口中比较出最大值后,删除第一个值(ans.removeFirst()),然后加入一个值;

需要借助lambda更快捷的取出最大值(lambda当作复习重点掌握吧)

上代码:

 public static ArrayList<integer> maxInWindows(int[] num, int size) {
        ArrayList<integer> res = new ArrayList<>();
        if(size<=0||size>num.length||num.length==0||num==null){return res;}
        Deque<integer> ans = new LinkedList<>();
     // 先将窗口塞满
        for (int i = 0; i < size; i++) {
            ans.add(num[i]);
        }
     // 取出最大值
        int max = ans.stream().mapToInt(Integer::intValue).max().getAsInt();
        res.add(max);
     // 删除窗口中第一个值
        ans.removeFirst();
        for (int i = size; i < num.length; i++) {// 窗口右侧抵达边界退出
            // 窗口中加入窗口后的值(理解为挪动一个位置)
            ans.add(num[i]);
           // 再次取出窗口中最大值
            int temp = ans.stream().mapToInt(Integer::intValue).max().getAsInt(); // 重点看下lambda表达式吧 省事很多
            res.add(temp);
            // 删除窗口的第一个值
            ans.removeFirst();
        }
        return res;
    }

　方案二:下标记录法（推荐）

思路:

每次选出最大值后,保存下标位置,之后的每次比较中,首先判断下标是否还在窗口中,如果在的话,只需要用下标位置的数和新加入的数比较一次就行了,如果不在那就整个窗口中比较出最大值.

上代码:

public static ArrayList<integer> maxInWindows(int[] num, int size) {
        ArrayList<integer> ans = new ArrayList<integer>();
        if (size > num.length || num == null || num.length == 0 || size == 0) {return ans;}
    // 最大值
        int max = num[0]; 
    // 记录下标
        int pos = 0;
    // 将窗口先填满,记录最大值,以及对应下标
        for (int i = 0; i < size; i++) {
            if (max < num[i]) {
                max = num[i];
                pos = i;
            }
        }
        ans.add(max);
    // 依次挪动窗口
        for (int i = size; i < num.length; i++) {
            if (i - size + 1 <= pos) {// 新窗口的第一个值 是否在最大值的下标前面
                if (num[i] > max) { //在的话  只需要判断新加入的第一个值 是否比最大值大
                    max = num[i];
                    pos = i;
                }
            } else {  //否则的话需要重写选举出最大值 上一个最大值已经滑过了
                max = num[i - size + 1]; //重新选举最大值 需要进行初始化
                for (int j = i - size + 1; j <= i; j++) {
                    if (num[j] > max) {
                        max = num[j];
                        pos = j;
                    }
                }
            }
            ans.add(max);
        }
        return ans;
    }

方案一:暴力容易理解,代码简洁,顺便复习Lambda表达式用法,额外用了size大小的空间，时间复杂度最好最坏都是O(n*k)

方案二:减少了比较次数,较方案一更优化，未用到额外空间，时间复杂度最好是O(n),最坏是O(n*k);

(k为窗口大小,n为数组长度)