专栏首页Java那些事每天一道剑指offer-滑动窗口的最大值

每天一道剑指offer-滑动窗口的最大值

滑动窗口的最大值

题目描述

给定一个数组和滑动窗口的大小,找出所有滑动窗口里数值的最大值。例如,如果输入数组{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]}。

public ArrayList<Integer> maxInWindows(int [] num, int size){
}

解析

使用一个单调非增队列,队头保存当前窗口的最大值,后面保存在窗口移动过程中导致队头失效(出窗口)后的从而晋升为窗口最大值的候选值。

public ArrayList<Integer> maxInWindows(int [] num, int size){    ArrayList<Integer> res = new ArrayList();    if(num == null || num.length == 0 || size <= 0 || size > num.length){        return res;    }
    //用队头元素保存窗口最大值,队列中元素只能是单调递减的,窗口移动可能导致队头元素失效    LinkedList<Integer> queue = new LinkedList();    int start = 0, end = size - 1;    for(int i = start ; i <= end ; i++){        addLast(queue, num[i]);    }    res.add(queue.getFirst());    //移动窗口    while(end < num.length - 1){        addLast(queue, num[++end]);        if(queue.getFirst() == num[start]){            queue.pollFirst();        }        start++;        res.add(queue.getFirst());    }
    return res;}
public void addLast(LinkedList<Integer> queue, int num){    if(queue == null){        return;    }    //加元素之前要确保该元素小于等于队尾元素    while(queue.size() != 0 && num > queue.getLast()){        queue.pollLast();    }    queue.addLast(num);}

出自:http://www.zhenganwen.top

已获授权

本文分享自微信公众号 - 程序员乔戈里(CXYqiaogeli)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-02-14

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 每天一道leetcode-105从前序和中序序列构建二叉树

    今天的题目 每天的题目见github(看最新的日期): https://github.com/gzc426

    乔戈里
  • SpringBoot+RabbitMQ ,保证消息100%投递成功并被消费(附源码)

    说明: 上面是核心代码, MsgLogService mapper xml等均未贴出, 完整代码可以参考GitHub上的源码,地址在文末。

    乔戈里
  • 每天一道剑指offer-按之字形顺序打印二叉树

    出处: https://www.nowcoder.com/questionTerminal/91b69814117f4e8097390d107d2efbe0

    乔戈里
  • hdu1002

    @坤的
  • Initial load DNL_CUST_PROD0 并找出SAP S4表和CRM表的mapping关系

    目标: Debug Outbound queue找出从Q7Q发送到QDD的数据。 Debug Inbound queue找出接受Q7Q传过来的数据,如何转换...

    Jerry Wang
  • 【Rust日报】 2019-08-08:q 框架 - 通用队列自动机运行时实现

    这个库的作用是这个,随着数据的增多,想要从各种数据中识别出用户的关键(敏感)信息,就越来越困难,必须使用一定的工具来进行自动化处理。而这个算法就在这个过程中起作...

    MikeLoveRust
  • 从Timer中学习优先队列的实现

    Timer是Java定时器的实现,用来调度定时执行的任务和执行一次的任务,就像JavaScript的setInterval和setTimeout的意思,它也可以...

    用户3579639
  • 如何自己实现一个队列

    队列是一种先进先出的数据结构,也是常见的数据结构之一。日常生活中的排队买东西就是一种典型的队列,而在购票系统也需要一个队列处理用户的购票请求,当然这里的队列就复...

    编程珠玑
  • 42. Python Queue 模

    Queue对象实现一个fifo队列(其他的还有lifo、priority队列,这里不再介绍)。

    py3study
  • 基于slim的残差网络

    slim中给出了resnet、vgg卷积网络的快速实现方法,定义的位置为:D:\anaconda\envs\tensorflow\Lib\site-packag...

    于小勇

扫码关注云+社区

领取腾讯云代金券