当前位置：首页 > article >正文

滑动窗口练习（一）— 固定窗口最大值问题

article 2024/11/15 13:36:50

题目
假设一个固定大小为W的窗口，依次划过arr，
返回每一次滑出状况的最大值
例如，arr = [4,3,5,4,3,3,6,7], W = 3
返回：[5,5,5,4,6,7]

暴力对数器
暴力对数器方法主要是用来做校验，不在乎时间复杂度，逻辑上能对即可，测试方法时采用大数据量和算法作对比，看是否有报错。
举例：此时数组arr = {3，1，5，7，6，5，8} w = 3。
从头开始遍历，当来到第一组3，1，5刚好凑齐w个数时，此时取Max，最大值为5。
继续向下，此时3过期来到1，5，7，取Max，最大值为7。
再次向后取值，1位置过期来到了5，7，6，取Max，最大值为7。
7，6，5最大值为7， 6，5，8最大值为8，所以最终答案为{5，7，7，7，8}。
在这里插入图片描述
代码
L从开始，R从w-1开始， L++R++，直到R到arr.length停止遍历，每次遍历都取L的最大值。将max赋值给result数组。

 public static int[] right(int[] arr, int w) {
        if (arr == null || w < 1 || arr.length < w) {
            return null;
        }

        int index = 0;
        int L = 0;
        int R = w - 1;
        int N = arr.length;
        int[] result = new int[arr.length - w + 1];
        while (R < N) {
            int max = arr[L];
            for (int i = L + 1; i <= R; i++) {
                max = Math.max(max, arr[i]);
            }
            result[index++] = max;
            L++;
            R++;
        }
        return result;
    }

滑动窗口
滑动窗口方法用LinkList来实现双端队列结构，不用过多考虑w个数，严格按照头 ——> 尾是从大到小的顺序即可。
变量R从0开始向arr.length遍历。
如果队列中不为null，并且新加入的元素大于等于队列尾端元素，就将满足条件的尾端元素全部弹出。而后将该元素加入到双端队列尾部。
当第一次R的下标来到了w - 1位置，证明已经遍历过了w个数，将此时队列头部最大值填充到新数组中。
如果当前头部最大值等于 R - w ，证明此时头部的值已经过期了，要剔除掉。

代码

 public static int[] getMaxWindow(int[] arr, int w) {
        if (arr == null || w < 1 || arr.length < w) {
            return null;
        }

        LinkedList<Integer> qmax = new LinkedList<>();
        int[] result = new int[arr.length - w + 1];
        int index = 0;

        for (int R = 0; R < arr.length; R++) {
            // 如果qmax双端队列不为null
            //并且尾端元素小于等于当前元素
            while (!qmax.isEmpty() && arr[qmax.peekLast()] <= arr[R]) {
                //满足条件的所有尾端元素全部弹出
                qmax.pollLast();
            }
            //将当前元素假如到队尾
            qmax.addLast(R);

            //R - w如果等于当前头部最大值
            //下一次循环R++ ，头部最大值要过期了，弹出
            if (R - w == qmax.peekFirst()) {
                qmax.pollFirst();
            }
            // R > w - 1，R从0开始，假设w = 3，则 w - 1 = 2说明此时窗口已经划过三个元素，该出现一个当前窗口最大值了
            if (R >= w - 1) {
                result[index++] = arr[qmax.peekFirst()];
            }
        }
        return result;
    }

测试
采用随机生成数组的方式，大样本量对两个方法进行测试。

 public static int[] generateRandomArray(int maxLength, int maxValue) {
        int[] arr = new int[(int) ((maxLength + 1) * Math.random())];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = (int) ((maxValue + 1) * Math.random());
        }
        return arr;
    }

    public static boolean isEqual(int[] arr1, int[] arr2) {
        if ((arr1 == null && arr2 != null) || (arr1 != null && arr2 == null)) {
            return false;
        }

        if (arr1 == null && arr2 == null) {
            return true;
        }

        if (arr1.length != arr2.length) {
            return false;
        }

        for (int i = 0; i < arr1.length; i++) {
            if (arr1[i] != arr2[i]) {
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        int maxValue = 100;
        int maxLength = 100;
        int testNum = 100000;

        for (int i = 0; i < testNum; i++) {
            int[] arr = generateRandomArray(maxLength, maxValue);
            int w = (int) (Math.random() * (arr.length + 1));

            int[] ans1 = getMaxWindow(arr, w);
            int[] ans2 = right(arr, w);

            if (!isEqual(ans1, ans2)) {
                System.out.println("w : " + w);
                for (int num : arr) {
                    System.out.print(num + " ");
                    break;
                }
            }
        }
    }