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

面试热题(滑动窗口最大值)

给你一个整数数组 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       31 [3  -1  -3] 5  3  6  7       31  3 [-1  -3  5] 3  6  7       51  3  -1 [-3  5  3] 6  7       51  3  -1  -3 [5  3  6] 7       61  3  -1  -3  5 [3  6  7]      7

 如果你刚看见这道题你会怎么想?三秒告诉我?3...2...1...,时间到!!!

       首先是滑动窗口,一听到这个名字,我们就应该立刻的想到双指针,双指针这个大方向是错不了,我们再看,要每次取到范围内的最大值,除了最大堆就是优先队列可以做到这件事,接下来我们先用最大堆进行解题

        最大堆就是其实就是一棵树,通过上浮和下浮使得堆顶是最大值或者最小值,Java中默认是最小堆,所以我们如果是想每次取到范围内的最大值,

  PriorityQueue<Integer> queue=new PriorityQueue<>(new Comparator<Integer>() {@Overridepublic int compare(Integer o1, Integer o2) {return o2-o1;//最大值   默认是o1-o2}});
wAAACH5BAEKAAAALAAAAAABAAEAAAICRAEAOw==

需要对堆的比较器进行重写,构造一个最大堆

 

 维护一个一个列表进行最大值的维护

List<Integer> list=new ArrayList<>();
wAAACH5BAEKAAAALAAAAAABAAEAAAICRAEAOw==
        for(int right=0;right< nums.length;right++){if(right<k-1){queue.offer(nums[right]);}else{queue.offer(nums[right]);list.add(queue.peek());queue.remove(nums[left++]);}}

结果,不出意外:

       怎么办?时间超时了怎么办?堆的上浮和下沉确实浪费了大量的时间,所以我们使用另外一种数据结构解决本题(优先队列)

    //维护一个单调队列class MaxQueue{private LinkedList<Integer> queue=new LinkedList<>();//添加public void push(int x){  //队列不为空,队尾元素如果小于当家加入元素,直接扔出去while(!queue.isEmpty()&&queue.getLast()<x){queue.pollLast();}queue.addLast(x);}//删除public void pop(int x){if(x==queue.getFirst()){queue.pollFirst();}}//得到最大值public Integer getMax(){return queue.getFirst();}}

 核心代码:

  int left=0;for(int right=0;right< nums.length;right++){if(right<k-1){window.push(nums[right]);}else{window.push(nums[right]);list.add(window.getMax());window.pop(nums[left++]);}}

结果,不出意外:

 上源代码:

  public int[] maxSlidingWindow(int[] nums, int k) {if(nums==null){return null;}MaxQueue window=new MaxQueue();List<Integer> list=new ArrayList<>();int left=0;for(int right=0;right< nums.length;right++){if(right<k-1){window.push(nums[right]);}else{window.push(nums[right]);list.add(window.getMax());window.pop(nums[left++]);}}return list.stream().mapToInt(Integer::valueOf).toArray();}//维护一个单调队列class MaxQueue{private LinkedList<Integer> queue=new LinkedList<>();//添加public void push(int x){while(!queue.isEmpty()&&queue.getLast()<x){queue.pollLast();}queue.addLast(x);}//删除public void pop(int x){if(x==queue.getFirst()){queue.pollFirst();}}//得到最大值public Integer getMax(){return queue.getFirst();}}

相关文章:

面试热题(滑动窗口最大值)

给你一个整数数组 nums&#xff0c;有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。 返回 滑动窗口中的最大值 。 输入&#xff1a;nums [1,3,-1,-3,5,3,6,7], k 3 输出&#xff1a;[3,3,5,…...

【代码】表格封装 + 高级查询 + 搜索 +分页器 (极简)

一、标题 查询条件按钮&#xff08;Header&#xff09; <!-- Header 标题搜索栏 --> <template><div><div class"header"><div class"h-left"><div class"title"><div class"desc-test">…...

ant.design 组件库中的 Tree 组件实现可搜索的树: React+and+ts

ant.design 组件库中的 Tree 组件实现可搜索的树&#xff0c;在这里我会详细介绍每个方法&#xff0c;以及容易踩坑的点。 效果图&#xff1a; 首先是要导入的文件 // React 自带的属性 import React, { useMemo, useState } from react; // antd 组件库中的&#xff0c;输入…...

Linux系统编程之信号(上)

一、信号概念 信号就是软件中断。每当程序收到一个信号&#xff0c;都需要按指定的方法去处理。以下是UNIX系统的信号表。 其中core表示产生一个复制了该进程内存映像的core文件&#xff0c;它保存了程序现场&#xff0c;可以使用gdb来调试。 二、signal() signal()函数用于改…...

23.Netty源码之内置解码器

highlight: arduino-light Netty内置的解码器 在前两节课我们介绍了 TCP 拆包/粘包的问题&#xff0c;以及如何使用 Netty 实现自定义协议的编解码。可以看到&#xff0c;网络通信的底层实现&#xff0c;Netty 都已经帮我们封装好了&#xff0c;我们只需要扩展 ChannelHandler …...

sigmoid ReLU 等激活函数总结

sigmoid ReLU sigoid和ReLU对比 1.sigmoid有梯度消失问题&#xff1a;当sigmoid的输出非常接近0或者1时&#xff0c;区域的梯度几乎为0&#xff0c;而ReLU在正区间的梯度总为1。如果Sigmoid没有正确初始化&#xff0c;它可能在正区间得到几乎为0的梯度。使模型无法有效训练。 …...

RabbitMQ 消息队列

文章目录 &#x1f370;有几个原因可以解释为什么要选择 RabbitMQ&#xff1a;&#x1f969;mq之间的对比&#x1f33d;RabbitMQ vs Apache Kafka&#x1f33d;RabbitMQ vs ActiveMQ&#x1f33d;RabbitMQ vs RocketMQ&#x1f33d;RabbitMQ vs Redis &#x1f969;linux docke…...

PHP实现在线进制转换器,10进制,2、4、8、16、32进制转换

1.接口文档 2.laravel实现代码 /*** 进制转换计算器* return \Illuminate\Http\JsonResponse*/public function binaryConvertCal(){$ten $this->request(ten);$two $this->request(two);$four $this->request(four);$eight $this->request(eight);$sixteen …...

报错 | Spring报错详解

Spring报错详解 一、前言二、报错提示三、分层解读1.最下面一层Caused by2.上一层Caused by3.最上层Caused by 四、总结五、解决方案 一、前言 本文主要是记录在初次学习Spring时遇到报错后的解读以及解决方案 二、报错提示 三、分层解读 遇到报错的时候&#xff0c;我们需要…...

PHP最简单自定义自己的框架数据库封装调用(五)

1、实现效果调用实现数据增删改查封装 2、index.php 入口定义数据库账号密码 <?php//定义当前请求模块 define("MODULE",index);//定义数据库 define(DB_HOST,localhost);//数据库地址 define(DB_DATABASE,aaa);//数据库 define(DB_USER,root);//数据库账号 def…...

使用Redis来实现点赞功能的基本思路

使用Redis来实现点赞功能是一种高效的选择&#xff0c;因为Redis是一个内存数据库&#xff0c;适用于处理高并发的数据操作。以下是一个基本的点赞功能在Redis中的设计示例&#xff1a; 假设我们有一个文章或帖子&#xff0c;用户可以对其进行点赞&#xff0c;取消点赞&#x…...

【黑马头条之app端文章搜索ES-MongoDB】

本笔记内容为黑马头条项目的app端文章搜索部分 目录 一、今日内容介绍 1、App端搜索-效果图 2、今日内容 二、搭建ElasticSearch环境 1、拉取镜像 2、创建容器 3、配置中文分词器 ik 4、使用postman测试 三、app端文章搜索 1、需求分析 2、思路分析 3、创建索引和…...

Nginx安装以及LVS-DR集群搭建

Nginx安装 1.环境准备 yum insatall -y make gcc gcc-c pcre-devel #pcre-devel -- pcre库 #安装openssl-devel yum install -y openssl-devel 2.tar安装包 3.解压软件包并创建软连接 tar -xf nginx-1.22.0.tar.gz -C /usr/local/ ln -s /usr/local/nginx-1.22.0/ /usr/local…...

后端开发9.商品类型模块

概述 简介 商品类型我设计的复杂了点,设计了多级类型 效果图 数据库设计...

spring框架自带的http工具RestTemplate用法

1. RestTemplate是什么&#xff1f; RestTemplate是由Spring框架提供的一个可用于应用中调用rest服务的类它简化了与http服务的通信方式。 RestTemplate是一个执行HTTP请求的同步阻塞式工具类&#xff0c;它仅仅只是在 HTTP 客户端库&#xff08;例如 JDK HttpURLConnection&a…...

【flink】Checkpoint expired before completing.

使用flink同步数据出现错误Checkpoint expired before completing. 11:32:34,455 WARN org.apache.flink.runtime.checkpoint.CheckpointFailureManager [Checkpoint Timer] - Failed to trigger or complete checkpoint 4 for job 1b1d41031ea45d15bdb3324004c2d749. (2 con…...

【论文阅读】NoDoze:使用自动来源分类对抗威胁警报疲劳(NDSS-2019)

NODOZE: Combatting Threat Alert Fatigue with Automated Provenance Triage 伊利诺伊大学芝加哥分校 Hassan W U, Guo S, Li D, et al. Nodoze: Combatting threat alert fatigue with automated provenance triage[C]//network and distributed systems security symposium.…...

【ARM64 常见汇编指令学习 16 -- ARM64 SMC 指令】

文章目录 ARMv8 同步异常同步异常指令SMC TYPE 上篇文章&#xff1a;ARM64 常见汇编指令学习 15 – ARM64 标志位的学习 下篇文章&#xff1a;ARM64 常见汇编指令学习 17 – ARM64 BFI 指令 ARMv8 同步异常 在ARMv8架构中&#xff0c;同步异常主要包括以下几种&#xff1a; Un…...

uprobe trace多线程mutex等待耗时

问题背景环境 ubuntu2204 服务器支持debugfs uprobe&#xff0c;为了提升应用程序的性能&#xff0c;需要量化不同参数下多线程主程序等待在mutex上的耗时区别 linux document中对uprobe events的说明如下 uprobetracer.rst - Documentation/trace/uprobetracer.rst - Linux…...

Linux 和 MacOS 中的 profile 文件详解(一)

什么是 profile 文件&#xff1f; profile 文件是 Linux、MacOS 等&#xff08;unix、类 unix 系统&#xff09;系统中的一种配置文件&#xff0c;主要用于设置系统和用户的环境变量。 在 shell 中&#xff0c;可以通过执行 profile 文件来设置用户的环境变量。shell 有两种运…...

IDEA运行Tomcat出现乱码问题解决汇总

最近正值期末周&#xff0c;有很多同学在写期末Java web作业时&#xff0c;运行tomcat出现乱码问题&#xff0c;经过多次解决与研究&#xff0c;我做了如下整理&#xff1a; 原因&#xff1a; IDEA本身编码与tomcat的编码与Windows编码不同导致&#xff0c;Windows 系统控制台…...

web vue 项目 Docker化部署

Web 项目 Docker 化部署详细教程 目录 Web 项目 Docker 化部署概述Dockerfile 详解 构建阶段生产阶段 构建和运行 Docker 镜像 1. Web 项目 Docker 化部署概述 Docker 化部署的主要步骤分为以下几个阶段&#xff1a; 构建阶段&#xff08;Build Stage&#xff09;&#xff1a…...

.Net框架,除了EF还有很多很多......

文章目录 1. 引言2. Dapper2.1 概述与设计原理2.2 核心功能与代码示例基本查询多映射查询存储过程调用 2.3 性能优化原理2.4 适用场景 3. NHibernate3.1 概述与架构设计3.2 映射配置示例Fluent映射XML映射 3.3 查询示例HQL查询Criteria APILINQ提供程序 3.4 高级特性3.5 适用场…...

(二)TensorRT-LLM | 模型导出(v0.20.0rc3)

0. 概述 上一节 对安装和使用有个基本介绍。根据这个 issue 的描述&#xff0c;后续 TensorRT-LLM 团队可能更专注于更新和维护 pytorch backend。但 tensorrt backend 作为先前一直开发的工作&#xff0c;其中包含了大量可以学习的地方。本文主要看看它导出模型的部分&#x…...

Golang dig框架与GraphQL的完美结合

将 Go 的 Dig 依赖注入框架与 GraphQL 结合使用&#xff0c;可以显著提升应用程序的可维护性、可测试性以及灵活性。 Dig 是一个强大的依赖注入容器&#xff0c;能够帮助开发者更好地管理复杂的依赖关系&#xff0c;而 GraphQL 则是一种用于 API 的查询语言&#xff0c;能够提…...

04-初识css

一、css样式引入 1.1.内部样式 <div style"width: 100px;"></div>1.2.外部样式 1.2.1.外部样式1 <style>.aa {width: 100px;} </style> <div class"aa"></div>1.2.2.外部样式2 <!-- rel内表面引入的是style样…...

Sklearn 机器学习 缺失值处理 获取填充失值的统计值

💖亲爱的技术爱好者们,热烈欢迎来到 Kant2048 的博客!我是 Thomas Kant,很开心能在CSDN上与你们相遇~💖 本博客的精华专栏: 【自动化测试】 【测试经验】 【人工智能】 【Python】 使用 Scikit-learn 处理缺失值并提取填充统计信息的完整指南 在机器学习项目中,数据清…...

热烈祝贺埃文科技正式加入可信数据空间发展联盟

2025年4月29日&#xff0c;在福州举办的第八届数字中国建设峰会“可信数据空间分论坛”上&#xff0c;可信数据空间发展联盟正式宣告成立。国家数据局党组书记、局长刘烈宏出席并致辞&#xff0c;强调该联盟是推进全国一体化数据市场建设的关键抓手。 郑州埃文科技有限公司&am…...

【把数组变成一棵树】有序数组秒变平衡BST,原来可以这么优雅!

【把数组变成一棵树】有序数组秒变平衡BST,原来可以这么优雅! 🌱 前言:一棵树的浪漫,从数组开始说起 程序员的世界里,数组是最常见的基本结构之一,几乎每种语言、每种算法都少不了它。可你有没有想过,一组看似“线性排列”的有序数组,竟然可以**“长”成一棵平衡的二…...

聚六亚甲基单胍盐酸盐市场深度解析:现状、挑战与机遇

根据 QYResearch 发布的市场报告显示&#xff0c;全球市场规模预计在 2031 年达到 9848 万美元&#xff0c;2025 - 2031 年期间年复合增长率&#xff08;CAGR&#xff09;为 3.7%。在竞争格局上&#xff0c;市场集中度较高&#xff0c;2024 年全球前十强厂商占据约 74.0% 的市场…...