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

滑动窗口练习(一)— 固定窗口最大值问题

题目
假设一个固定大小为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;
                }
            }
        }
    }

http://www.kler.cn/news/133781.html

相关文章:

  • LinkWeChat V4.9.8 版本发布
  • HCIA-综合实验(三)
  • linux 邮箱配置
  • 十、Linux运行级别
  • 创芯科技USB_CAN【库文件】
  • Network(四)NAT实现方式与VRRP概述
  • SQL编写规范【干货】
  • YOLOv8改进 | 如何在网络结构中添加注意力机制、C2f、卷积、Neck、检测头
  • MySQL进阶_9.事务基础知识
  • Redis哨兵模式(Docker)
  • 抽象工厂模式-C++实现
  • 当小白遇到电脑程序不完全退出怎么办?
  • kubernetes--Pod控制器详解
  • 【Java并发编程六】多线程越界问题
  • nginx 如何根据IP做限流,以及 nginx 直接返回 json 格式数据
  • 深信服AC密码认证(外部认证:LDAP认证)
  • C#中委托和事件的使用总结
  • JDK1.5 新特性【反射】
  • 大数据基础设施搭建 - ZooKeeper
  • 漏洞利用工具的编写
  • kafka 磁盘扩容与数据均衡实在操作讲解
  • K-Means算法进行分类
  • 2342. 数位和相等数对的最大和 --力扣 --JAVA
  • MySQL数据库下的Explain命令深度解析
  • 自动驾驶学习笔记(九)——车辆控制
  • .NET 8 正式 GA 遥遥领先
  • kaggle新赛:SenNet 3D肾脏分割大赛(3D语义分割)
  • windows 安装 Oracle Database 19c
  • WPF如何实现应用程序托盘
  • 【算法日志】图论 并查集及其简单应用