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

滑动窗口的最大值

http://www.nowcoder.com/practice/1624bc35a45c42c0bc17d17fa0cba788

描述

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

解题思路

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

image-20210621195527937

方案一:暴力法

思路:

使用双端队列来做,每次保证队列长度为窗口大小,在一个窗口中比较出最大值后,删除第一个值(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为数组长度)

全部评论
为什么会滑过去
点赞 回复 分享
发布于 2022-11-05 23:17 广东

相关推荐

就前几天旅游的时候,打开抖音就经常刷到这类视频:以前是高学历学生、老师、主持人,现在做着团播、擦边主播的工作,以及那些经过精心包装的“职业转型”故事——从铺天盖地的VLOG到所谓的“04年夜场工作日记”,这些内容在初中升学、高考放榜等关键时间节点持续发酵。可以说非常直接且精准地在潜移默化地影响着心智尚未成熟的青少年,使其对特殊行业逐渐脱敏。那我就想问了:某些传播公司、平台运营者甚至某些夜场的老板,你们究竟在传递怎样的价值观?点开那些视频,评论区里也是呈现明显的两极分化:一种是​​经济下行论​​:“现在就业市场已经艰难到这种程度了吗?”​​一种是事实反驳派​​:这些创作者往往拥有名校背景,从事着...
牛客刘北:被环境教育的,为了能拿到足够的钱养活自己,不甘心也得甘心,现在的短视频传播的思想的确很扭曲,但是很明显,互联网玩上一年你就能全款提A6,但你全心全意不吃不喝工作一年未必能提A6,但是在高考中考出现这个的确很扭曲,在向大家传播“不上学,玩互联网也可以轻松年入百万”,不是人变了,是社会在变
预测一下26届秋招形势
点赞 评论 收藏
分享
06-12 10:50
门头沟学院 Java
你的不定积分没加C:我怎么在学院群看到了同样的话
点赞 评论 收藏
分享
后来123321:别着急,我学院本大二,投了1100份,两个面试,其中一个还是我去线下招聘会投的简历,有时候这东西也得看运气
无实习如何秋招上岸
点赞 评论 收藏
分享
07-01 17:14
中北大学 Java
兄弟们是真是假
牛客46374834...:我在boss上投java岗从来没成功过
点赞 评论 收藏
分享
评论
3
2
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务