Leetcode 239题 滑动窗口最大值(Sliding Window Maximum) Java语言求解

Stella981
• 阅读 349

题目链接

https://leetcode-cn.com/problems/sliding-window-maximum/

题目内容

给定一个数组 nums,有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。

返回滑动窗口中的最大值。

输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3
输出: [3,3,5,5,6,7]
解释:
滑动窗口的位置|最大值 -|- [1 3 -1] -3 5 3 6 7|3| 1 [3 -1 -3] 5 3 6 7|3| 1 3 [-1 -3 5] 3 6 7| 5| 1 3 -1 [-3 5 3] 6 7| 5| 1 3 -1 -3 [5 3 6] 7|6| 1 3 -1 -3 5 [3 6 7]|7|

分析

1、创建一个双端队列用来存储nums数组中元素的索引; 2、创建一个结果数组存储达到窗口大小时,在窗口内的元素; 3、没达到窗口大小时:如果双端队列是空的,那么直接从队尾插入元素的索引,如果双端队列不为空,需要保证双端队列中的索引在nums中的值是递减的。达到窗口大小时,直接将双端队列的头部元素在nums中的值存储到结果数组。

如图: 先放动态图:

Leetcode 239题 滑动窗口最大值(Sliding Window Maximum) Java语言求解

再放静态图;

Leetcode 239题 滑动窗口最大值(Sliding Window Maximum) Java语言求解 Leetcode 239题 滑动窗口最大值(Sliding Window Maximum) Java语言求解 Leetcode 239题 滑动窗口最大值(Sliding Window Maximum) Java语言求解

Leetcode 239题 滑动窗口最大值(Sliding Window Maximum) Java语言求解 Leetcode 239题 滑动窗口最大值(Sliding Window Maximum) Java语言求解 Leetcode 239题 滑动窗口最大值(Sliding Window Maximum) Java语言求解

Leetcode 239题 滑动窗口最大值(Sliding Window Maximum) Java语言求解 Leetcode 239题 滑动窗口最大值(Sliding Window Maximum) Java语言求解 Leetcode 239题 滑动窗口最大值(Sliding Window Maximum) Java语言求解

Leetcode 239题 滑动窗口最大值(Sliding Window Maximum) Java语言求解

Leetcode 239题 滑动窗口最大值(Sliding Window Maximum) Java语言求解

Leetcode 239题 滑动窗口最大值(Sliding Window Maximum) Java语言求解

Leetcode 239题 滑动窗口最大值(Sliding Window Maximum) Java语言求解

Leetcode 239题 滑动窗口最大值(Sliding Window Maximum) Java语言求解

Leetcode 239题 滑动窗口最大值(Sliding Window Maximum) Java语言求解

Leetcode 239题 滑动窗口最大值(Sliding Window Maximum) Java语言求解

Leetcode 239题 滑动窗口最大值(Sliding Window Maximum) Java语言求解

Leetcode 239题 滑动窗口最大值(Sliding Window Maximum) Java语言求解

Leetcode 239题 滑动窗口最大值(Sliding Window Maximum) Java语言求解

Leetcode 239题 滑动窗口最大值(Sliding Window Maximum) Java语言求解

Leetcode 239题 滑动窗口最大值(Sliding Window Maximum) Java语言求解

Leetcode 239题 滑动窗口最大值(Sliding Window Maximum) Java语言求解

Leetcode 239题 滑动窗口最大值(Sliding Window Maximum) Java语言求解

Leetcode 239题 滑动窗口最大值(Sliding Window Maximum) Java语言求解

Leetcode 239题 滑动窗口最大值(Sliding Window Maximum) Java语言求解

Leetcode 239题 滑动窗口最大值(Sliding Window Maximum) Java语言求解

代码

import jdk.jshell.spi.ExecutionControl;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        if(nums.length<=0)
            throw new RuntimeException("nums是空的!");
        //创建双端队列
        Deque<Integer> deque = new LinkedList<>();
        //创建一个结果的ArrayList
        ArrayList<Integer> resut_array = new ArrayList<>();
        for(int i=0;i<nums.length;i++){
            //如果双端队列不为空,而且到了窗口长度
            if(!deque.isEmpty() && deque.peek() == i-k)
                //移除第一个元素
                deque.pollFirst();
            //保证nums【双端队列中的索引】是一个递减数列
            while(!deque.isEmpty() && nums[deque.getLast()] < nums[i])
                deque.pollLast();

            //把当前元素的索引加到双端队列中
            deque.offer(i);
            //如果是窗口大小
            if(i >= k-1)
                resut_array.add(nums[deque.peek()]);
        }

        //ArrayList转换成整型数组
        int[] res = resut_array.stream().mapToInt(Integer::intValue).toArray();
        return res;
    }
}

欢迎关注

欢迎大家的关注

扫描下方的二维码关注我的微信公众号:code随笔 Leetcode 239题 滑动窗口最大值(Sliding Window Maximum) Java语言求解

点赞
收藏
评论区
推荐文章
秃头王路飞 秃头王路飞
6个月前
webpack5手撸vue2脚手架
webpack5手撸vue相信工作个12年的小伙伴们在面试的时候多多少少怕被问到关于webpack方面的知识,本菜鸟最近闲来无事,就尝试了手撸了下vue2的脚手架,第一次发帖实在是没有经验,望海涵。languageJavaScript"name":"vuecliversion2","version":"1.0.0","desc
blmius blmius
1年前
MySQL:[Err] 1292 - Incorrect datetime value: ‘0000-00-00 00:00:00‘ for column ‘CREATE_TIME‘ at row 1
文章目录问题用navicat导入数据时,报错:原因这是因为当前的MySQL不支持datetime为0的情况。解决修改sql\mode:sql\mode:SQLMode定义了MySQL应支持的SQL语法、数据校验等,这样可以更容易地在不同的环境中使用MySQL。全局s
光头强的博客 光头强的博客
6个月前
Java面向对象试题
1、请创建一个Animal动物类,要求有方法eat()方法,方法输出一条语句“吃东西”。创建一个接口A,接口里有一个抽象方法fly()。创建一个Bird类继承Animal类并实现接口A里的方法输出一条有语句“鸟儿飞翔”,重写eat()方法输出一条语句“鸟儿吃虫”。在Test类中向上转型创建b对象,调用eat方法。然后向下转型调用eat()方
刚刚好 刚刚好
6个月前
css问题
1、在IOS中图片不显示(给图片加了圆角或者img没有父级)<div<imgsrc""/</divdiv{width:20px;height:20px;borderradius:20px;overflow:h
小森森 小森森
3天前
租房类微信小程序-基于微信云开发-小程序端集成了管理员后台-一键部署,快速发布
温馨提醒本项目使用MITLicense协议,仅适用于学习交流,并且不提供无偿的、不提供无偿的、不提供无偿的维护修改服务(但可提issue)。若直接将本项目用于商用,因本项目带来的所有后果由使用者自行承担。如需商用升级版,请联系我微信,微信二维码在本博客页面右上角在此奉劝某些人,请尊重作者的劳动成果,做人积点德吧!最近发现有人拿我的源码进行二次分
小森森 小森森
3天前
计划助手V1.0-微信小程序(QQ小程序)-源代码分享
疫情期间在家感觉好无聊啊,于是利用空闲时间做了一个用来记录和管理小目标时间的小程序,命名为《小沙漏》。QQ版本小程序同步上线,QQ小程序叫《时间小沙漏》,欢迎大家前来体验,后期也会添加其他的新功能哦【区别】:微信小程序的代码与QQ小程序的源码是不一样的。微信小程序的源码基于微信小程序云开发,需要在有网络的情况下使用,具有同步功能,所有记录在删除小
小森森 小森森
6个月前
校园表白墙微信小程序V1.0 SayLove -基于微信云开发-一键快速搭建,开箱即用
后续会继续更新,敬请期待2.0全新版本欢迎添加左边的微信一起探讨!项目地址:(https://www.aliyun.com/activity/daily/bestoffer?userCodesskuuw5n)\2.Bug修复更新日历2.情侣脸功能大家不要使用了,现在阿里云的接口已经要收费了(土豪请随意),\\和注意
晴空闲云 晴空闲云
6个月前
css中box-sizing解放盒子实际宽高计算
我们知道传统的盒子模型,如果增加内边距padding和边框border,那么会撑大整个盒子,造成盒子的宽度不好计算,在实务中特别不方便。boxsizing可以设置盒模型的方式,可以很好的设置固定宽高的盒模型。盒子宽高计算假如我们设置如下盒子:宽度和高度均为200px,那么这会这个盒子实际的宽高就都是200px。但是当我们设置这个盒子的边框和内间距的时候,那
艾木酱 艾木酱
5个月前
快速入门|使用MemFire Cloud构建React Native应用程序
MemFireCloud是一款提供云数据库,用户可以创建云数据库,并对数据库进行管理,还可以对数据库进行备份操作。它还提供后端即服务,用户可以在1分钟内新建一个应用,使用自动生成的API和SDK,访问云数据库、对象存储、用户认证与授权等功能,可专
NVIDIA安培架构下MIG技术分析
关键词:NVIDIA、MIG、安培一什么是MIG2020年5月,NVIDIA发布了最新的GPU架构:安培,以及基于安培架构的最新的GPU:A100。安培提供了许多新的特性,MIG是其中一项非常重要的新特性。MIG的全名是MultiInstanceGPU。NVIDIA安培架构中的MIG模式可以在A100GPU上并行运行七个作业。多实
helloworld_28799839 helloworld_28799839
6个月前
常用知识整理
Javascript判断对象是否为空jsObject.keys(myObject).length0经常使用的三元运算我们经常遇到处理表格列状态字段如status的时候可以用到vue