当前位置: 首页 > 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 有两种运…...

生成xcframework

打包 XCFramework 的方法 XCFramework 是苹果推出的一种多平台二进制分发格式&#xff0c;可以包含多个架构和平台的代码。打包 XCFramework 通常用于分发库或框架。 使用 Xcode 命令行工具打包 通过 xcodebuild 命令可以打包 XCFramework。确保项目已经配置好需要支持的平台…...

地震勘探——干扰波识别、井中地震时距曲线特点

目录 干扰波识别反射波地震勘探的干扰波 井中地震时距曲线特点 干扰波识别 有效波&#xff1a;可以用来解决所提出的地质任务的波&#xff1b;干扰波&#xff1a;所有妨碍辨认、追踪有效波的其他波。 地震勘探中&#xff0c;有效波和干扰波是相对的。例如&#xff0c;在反射波…...

R语言AI模型部署方案:精准离线运行详解

R语言AI模型部署方案:精准离线运行详解 一、项目概述 本文将构建一个完整的R语言AI部署解决方案,实现鸢尾花分类模型的训练、保存、离线部署和预测功能。核心特点: 100%离线运行能力自包含环境依赖生产级错误处理跨平台兼容性模型版本管理# 文件结构说明 Iris_AI_Deployme…...

2024年赣州旅游投资集团社会招聘笔试真

2024年赣州旅游投资集团社会招聘笔试真 题 ( 满 分 1 0 0 分 时 间 1 2 0 分 钟 ) 一、单选题(每题只有一个正确答案,答错、不答或多答均不得分) 1.纪要的特点不包括()。 A.概括重点 B.指导传达 C. 客观纪实 D.有言必录 【答案】: D 2.1864年,()预言了电磁波的存在,并指出…...

精益数据分析(97/126):邮件营销与用户参与度的关键指标优化指南

精益数据分析&#xff08;97/126&#xff09;&#xff1a;邮件营销与用户参与度的关键指标优化指南 在数字化营销时代&#xff0c;邮件列表效度、用户参与度和网站性能等指标往往决定着创业公司的增长成败。今天&#xff0c;我们将深入解析邮件打开率、网站可用性、页面参与时…...

有限自动机到正规文法转换器v1.0

1 项目简介 这是一个功能强大的有限自动机&#xff08;Finite Automaton, FA&#xff09;到正规文法&#xff08;Regular Grammar&#xff09;转换器&#xff0c;它配备了一个直观且完整的图形用户界面&#xff0c;使用户能够轻松地进行操作和观察。该程序基于编译原理中的经典…...

零基础在实践中学习网络安全-皮卡丘靶场(第九期-Unsafe Fileupload模块)(yakit方式)

本期内容并不是很难&#xff0c;相信大家会学的很愉快&#xff0c;当然对于有后端基础的朋友来说&#xff0c;本期内容更加容易了解&#xff0c;当然没有基础的也别担心&#xff0c;本期内容会详细解释有关内容 本期用到的软件&#xff1a;yakit&#xff08;因为经过之前好多期…...

Mysql中select查询语句的执行过程

目录 1、介绍 1.1、组件介绍 1.2、Sql执行顺序 2、执行流程 2.1. 连接与认证 2.2. 查询缓存 2.3. 语法解析&#xff08;Parser&#xff09; 2.4、执行sql 1. 预处理&#xff08;Preprocessor&#xff09; 2. 查询优化器&#xff08;Optimizer&#xff09; 3. 执行器…...

Selenium常用函数介绍

目录 一&#xff0c;元素定位 1.1 cssSeector 1.2 xpath 二&#xff0c;操作测试对象 三&#xff0c;窗口 3.1 案例 3.2 窗口切换 3.3 窗口大小 3.4 屏幕截图 3.5 关闭窗口 四&#xff0c;弹窗 五&#xff0c;等待 六&#xff0c;导航 七&#xff0c;文件上传 …...

C#学习第29天:表达式树(Expression Trees)

目录 什么是表达式树&#xff1f; 核心概念 1.表达式树的构建 2. 表达式树与Lambda表达式 3.解析和访问表达式树 4.动态条件查询 表达式树的优势 1.动态构建查询 2.LINQ 提供程序支持&#xff1a; 3.性能优化 4.元数据处理 5.代码转换和重写 适用场景 代码复杂性…...