每日一题(LeetCode)----栈和队列--滑动窗口最大值
每日一题(LeetCode)----栈和队列–滑动窗口最大值
1.题目(239. 滑动窗口最大值)
-
给你一个整数数组
nums
,有一个大小为k
的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的k
个数字。滑动窗口每次只向右移动一位。返回 滑动窗口中的最大值 。
示例 1:
输入: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
示例 2:
输入:nums = [1], k = 1 输出:[1]
提示:
1 <= nums.length <= 105
-104 <= nums[i] <= 104
1 <= k <= nums.length
2.解题思路
思路一:使用优先队列
优先队列的底层实现是堆,默认是大顶堆
1.我们先创建一个优先队列底层是大顶堆的,便于我们维护最大值,且这个优先队列中的每一个元素都是二元组的(每一个二元组的元素的第一个表示的是数组中的一个数,第二个表示的是这个数在数组中对应的下标),便于我们之后将不在滑动窗口范围内的元素删除 然后再创建一个动态数组用来存每一个滑动窗口的最大值
2.初始时,我们先根据k变量的大小,把数组的前k个元素连带着它们的下标放入到优先队列中去
3.我们从第k+1个元素开始向后遍历,每遍历到一个元素,将当前元素连带着它的下标作为一个二元组元素放入到优先队列中去,然后将优先队列的首元素中存的下标与当前滑动窗口的左边界进行比较如果比左边界小那么就删除当前优先队列的首元素直到优先队列的首元素中存的下标比左边界大结束,然后将当前优先队列首元素存的值放入到动态数组中去,继续向后遍历
在滑动窗口中,在这种情况下,这个值在数组 nums\textit{nums}nums 中的位置出现在滑动窗口左边界的左侧。因此,当我们后续继续向右移动窗口时,这个值就永远不可能出现在滑动窗口中了,我们可以将其永久地从优先队列中移除。
我们不断地移除堆顶的元素,直到其确实出现在滑动窗口中。此时,堆顶元素就是滑动窗口中的最大值。
思路来源:力扣官方题解
链接:https://leetcode.cn/problems/sliding-window-maximum/
思路二:双向队列(单调队列)
1.我们先创建一个双向队列(单调队列),这个队列存的是数组中元素的下标,我们要保证这个队列中存的元素的下标对应的数是递减的,然后我们再创建一个动态数组用来存每一个滑动窗口的最大值
2.初始时,我们先根据k变量的大小,先对数组中前k个元素进行处理,当队列为空时,我们直接把当前遍历到的元素对应的下标放入到队列末尾,当队列不为空时,且当前遍历到的元素的值大于队列末尾下标所对应的数的值,那么我们删除队列的末尾元素,继续与队列末尾元素进行比较,直到当前遍历到的元素的值小于队列末尾下标所对应的数的值,我们将当前元素对应的下标放入到队列的末尾
3.我们从第k+1个元素开始向后遍历,每遍历到一个元素,看队列是否为空,当队列为空时,我们直接把当前遍历到的元素对应的下标放入到队列末尾,当队列不为空时,且当前遍历到的元素的值大于队列末尾下标所对应的数的值,那么我们删除队列的末尾元素,继续与队列末尾元素进行比较,直到当前遍历到的元素的值小于队列末尾下标所对应的数的值,我们将当前元素对应的下标放入到队列的末尾,再将队列的首元素的值与当前滑动窗口的左边界进行比较,如果比左边界小那么就删除当前队列的首元素直到队列的首元素的值比左边界大结束,然后将当前队列首元素在数组中对应的值放入到动态数组中去,继续向后遍历
思路来源:力扣官方题解
链接:https://leetcode.cn/problems/sliding-window-maximum/
3.写出代码
思路一的代码
class Solution {
public:vector<int> maxSlidingWindow(vector<int>& nums, int k) {priority_queue<pair<int,int>> q;int n=nums.size();for(int i=0;i<k;i++){q.emplace(nums[i],i);}vector<int> ans={q.top().first};for(int i=k;i<n;i++){q.emplace(nums[i],i);while(q.top().second<=i-k){q.pop();}ans.push_back(q.top().first);}return ans;}
};
思路来源:力扣官方题解
链接:https://leetcode.cn/problems/sliding-window-maximum/
思路二的代码
class Solution {
public:vector<int> maxSlidingWindow(vector<int>& nums, int k) {deque<int> q;int n=nums.size();for(int i=0;i<k;i++){while(!q.empty()&&nums[i]>=nums[q.back()]){q.pop_back();}q.push_back(i);}vector<int> ans={nums[q.front()]};for(int i=k;i<n;i++){while(!q.empty()&&nums[i]>=nums[q.back()]){q.pop_back();}q.push_back(i);while(q.front()<=i-k){q.pop_front();}ans.push_back(nums[q.front()]);}return ans;}
};
思路来源:力扣官方题解
链接:https://leetcode.cn/problems/sliding-window-maximum/
相关文章:
每日一题(LeetCode)----栈和队列--滑动窗口最大值
每日一题(LeetCode)----栈和队列–滑动窗口最大值 1.题目(239. 滑动窗口最大值) 给你一个整数数组 nums,有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。 …...
13.bash shell中的if-then语句
文章目录 shell中的流控制if语句if语句if-then语句if-then-else 语句 test命令数值比较字符串比较文件比较case语句 欢迎访问个人网络日志🌹🌹知行空间🌹🌹 shell中的流控制if语句 简单的脚本可以只包含顺序执行的命令࿰…...
深入了解 Python 的 import 语句
在 Python 中,import 语句是一个关键的功能,用于在程序中引入模块和包。本文将深入讨论 import 语句的各种用法、注意事项以及一些高级技巧,以帮助你更好地理解和使用这一功能。 概念介绍 package 通常对应一个文件夹,下面可以有…...
接口测试 — 11.logging日志模块处理流程
1、概括理解 了解了四大组件的基本定义之后,我们通过图示的方式来理解下信息的传递过程: 也就是获取的日志信息,进入到Logger日志器中,传递给处理器确定要输出到哪里,然后进行过滤器筛选,通过后再按照定义…...
Hago 的 Spark on ACK 实践
作者:华相 Hago 于 2018 年 4 月上线,是欢聚集团旗下的一款多人互动社交明星产品。Hago 融合优质的匹配能力和多样化的垂类场景,提供互动游戏、多人语音、视频直播、 3D 虚拟形象互动等多种社交玩法,致力于为用户打造高效、多样、…...
mac传输文件到windows
前言 由于mac系统与windows系统文件格式不同,通过U盘进行文件拷贝时,导致无法拷贝。官方解决方案如下,但是描述的比较模糊。看我的操作步骤即可。 https://support.apple.com/zh-cn/guide/mac-help/mchlp1657/12.0/mac/12.6 前提条件 mac与…...
trtc-electron-sdk的demo中添加更新功能以及出现的报错问题
1、官网demo下载地址 点击下载 按照官网demo说明文档进行安装和运行 2、添加electron-updater npm install electron-updater根据项目需求安装对应的版本,建议使用5.2.1 3、创建一个handleUpdater.js文件,和package.json同级 // const { ipcMain } …...
什么是流量攻击? 流量攻击怎么处理?
由于DDoS攻击往往采取合法的数据请求技术,再加上傀儡机器,造成DDoS攻击成为最难防御的网络攻击之一。据美国最新的安全损失调查报告,DDoS攻击所造成的经济损失已经跃居第一。 传统的网络设备和周边安全技术,例如防火墙和IDSs(Intr…...
【大数据】NiFi 的基本使用
NiFi 的基本使用 1.NiFi 的安装与使用1.1 NiFi 的安装1.2 各目录及主要文件 2.NiFi 的页面使用2.1 主页面介绍2.2 面板介绍 3.NiFi 的工作方式3.1 基本方式3.2 选择处理器3.3 组件状态3.4 组件的配置3.4.1 SETTINGS(通用配置)3.4.2 SCHEDULING࿰…...
5 分钟内搭建一个免费问答机器人:Milvus + LangChain
搭建一个好用、便宜又准确的问答机器人需要多长时间? 答案是 5 分钟。只需借助开源的 RAG 技术栈、LangChain 以及好用的向量数据库 Milvus。必须要强调的是,该问答机器人的成本很低,因为我们在召回、评估和开发迭代的过程中不需要调用大语言…...
WPF Border
在 WPF 中,Border 是一种常用的控件,用于给其他控件提供边框和背景效果。 要使用 Border 控件,您可以在 XAML 代码中添加以下代码: <Border BorderBrush"Black" BorderThickness"2" Background"Lig…...
基于博弈树的开源五子棋AI教程[4 静态棋盘评估]
引子 静态棋盘的评估是棋力的一个很重要的体现,一个优秀的基于博弈树搜索的AI往往有上千行工作量,本文没有做深入讨论,仅仅写了个引子用来抛砖引玉。 评估一般从两个角度入手,一个是子力,另一个是局势。 1 评估维度 …...
STL--排序与检索
题目 现有N个大理石,每个大理石上写了一个非负整数。首先把各数从小到大排序,然后回答Q个问题。每个问题是否有一个大理石写着某个整数x,如果是,还要回答哪个大理石写着x。排序后的大理石从左到右编写为1-N。(样例中,…...
大数据处理与分析-Spark
导论 (基于Hadoop的MapReduce的优缺点) MapReduce是一个分布式运算程序的编程框架,是用户开发“基于Hadoop的数据分析应用”的核心框架 MapReduce是一种用于处理大规模数据集的编程模型和计算框架。它将数据处理过程分为两个主要阶段:Map阶…...
虚拟机的下载、安装(模拟出服务器)
下载 vmware workstation(收费的虚拟机) 下载vbox 网址:Oracle VM VirtualBox(免费的虚拟机) 以下选择一个下载即可,建议下载vbox,因为是免费的。安装的时候默认下一步即可(路径最好…...
K8S Pod Terminating/Unknown故障排查
一、pod异常出现现象 优雅终止周期(Graceful termination period): 当pod被删除时,会进入"Terminating"状态,等待容器优雅关闭。如果容器关闭所需时间超过默认期限(默认30秒),则pod将保持在"Terminating"状态。 Finalize…...
labelme标注的json文件数据转成coco数据集格式(可处理目标框和实例分割)
这里主要是搬运一下能找到的 labelme标注的json文件数据转成coco数据集格式(可处理目标框和实例分割)的代码,以供需要时参考和提供相关帮助。 1、官方labelme实现 如下是labelme官方网址,提供了源代码,以及相关使用方…...
MySQL报错:1366 - Incorrect integer value: ‘xx‘ for column ‘xx‘ at row 1的解决方法
我在插入表数据时遇到了1366报错,报错内容:1366 - Incorrect integer value: Cindy for column name at row 1,下面我演示解决方法。 根据上图,原因是Cindy’对应的name字段数据类型不正确。我们在左侧找到该字段所在的grade_6表&…...
MySQL中MVCC的流程
参考文章一 参考文章二 当谈到数据库的并发控制时,多版本并发控制(MVCC)是一个重要的概念。MVCC 是一种用于实现数据库事务隔离性的技术,常见于像 PostgreSQL 和 Oracle 这样的数据库系统中。 MVCC 的核心思想是为每个数据行维护…...
朴素贝叶斯法_naive_Bayes
朴素贝叶斯法(naive Bayes)是基于贝叶斯定理与特征条件独立假设的分类方法。对于给定的训练数据集,首先基于特征条件独立假设学习输入输出的联合概率分布;然后基于此模型,对给定的输入 x x x,利用贝叶斯定理…...
Windows下安装MongoDB实践总结
本文记录Windows环境下的MongoDB安装与使用总结。 【1】官网下载 官网下载地址:Download MongoDB Community Server | MongoDB 这里可以选择下载zip或者msi,zip是解压后自己配置,msi是傻瓜式一键安装。这里我们分别对比进行实践。 【2】ZI…...
华为云Stack 8.X 流量模型分析(二)
二、流量模型分析相关知识 1.vNIC 虚拟网络接口卡(vNIC)是基于主机物理 NIC 的虚拟网络接口。每个主机可以有多个 NIC,每个 NIC 可以是多个 vNIC 的基础。 将 vNIC 附加到虚拟机时,Red Hat Virtualization Manager 会在虚拟机之间创建多个关联的…...
rk3588 之启动
目录 uboot版本配置修改编译 linux版本配置修改编译 启动sd卡启动制作spi 烧录 参考 uboot 版本 v2024.01-rc2 https://github.com/u-boot/u-boot https://github.com/rockchip-linux/rkbin 配置修改 使用这两个配置即可: orangepi-5-plus-rk3588_defconfig r…...
ARM GIC (五)gicv3架构-LPI
在gicv3中,引入了一种新的中断类型。message based interrupts,消息中断。 一、消息中断 外设,不在通过专用中断线,向gic发送中断,而是写gic的寄存器,来发送中断。 这样的一个好处是,可以减少中断线的个数。 为了支持消息中断,gicv3,增加了LPI,来支持消息中断。并且…...
sql-labs服务器结构
双层服务器结构 一个是tomcat的jsp服务器,一个是apache的php服务器,提供服务的是php服务器,只是tomcat向php服务器请求数据,php服务器返回数据给tomcat。 此处的29-32关都是这个结构,不是用docker拉取的镜像要搭建一下…...
【小沐学写作】Docsify制作在线电子书、技术文档(Docsify + Markdown + node)
文章目录 1、简介2、安装2.1 node2.2 docsify-cli 3、配置3.1 初始化3.2 预览效果3.3 加载对话框3.4 更多页面3.5 侧 栏3.6 自定义导航栏 结语 1、简介 https://docsify.js.org/#/?iddocsify 一个神奇的文档网站生成器。 简单轻巧没有静态构建的 html 文件多个主题 Docsify…...
电脑完全重装教程——原版系统镜像安装
注意事项 本教程会清除所有个人文件 请谨慎操作 请谨慎操作 请谨慎操作 前言 本教程是以系统安装U盘为介质进行系统重装操作,照着流程操作会清除整个硬盘里的文件,请考虑清楚哦~ 有些小伙伴可能随便在百度上找个WinPE作为启动盘就直接…...
【智慧办公】如何让智能会议室的电子标签实现远程、批量更新信息?东胜物联网硬件网关让解决方案更具竞争力
近年来,为了减少办公耗能、节能环保、降本增效,越来越多的企业开始从传统的办公模式转向智慧办公。 以智能会议室为例,会议是企业业务中不可或缺的一部分,但在传统办公模式下,一来会议前行政人员需要提前准备会议材料…...
面向对象设计与分析40讲(16)静态工厂方法模式
前面我们介绍了简单工厂模式,在创建对象前,我们需要先创建工厂,然后再通过工厂去创建产品。 如果将工厂的创建方法static化,那么无需创建工厂即可通过静态方法直接调用的方式创建产品: // 工厂类,定义了静…...
【贪心】买卖股票的最佳时机含手续费
/** 贪心:每次选取更低的价格买入,遇到高于买入的价格就出售(此时不一定是最大收益)。* 使用buy表示买入股票的价格和手续费的和。遍历数组,如果后面的股票价格加上手续费* 小于buy,说明有更低的买入价格更新buy。如…...
Altium Designer入门到就业【目录】
🏡《AD目录》 欢迎大家来到《Altium Designer入门到就业》该专栏包括【电路设计篇】【PCB设计篇】【电路仿真篇】【PCB仿真篇】四个部分,以供大家参考。大家直接点击大纲中蓝色标题即可轻松传送。 【电路设计篇】 Altium Designer(AD24&#…...
cmake 查看编译命令,以及在vscode中如何使用cmke
通过设置如下配置选项,可以生成compile_commands.json 文件,记录使用的编译命令 set(CMAKE_EXPORT_COMPILE_COMMANDS ON)获得现有模块列表 cmake --help-module-list查看命令文档 cmake --help-command find_file查看模块的详细信息 cmake --help-mo…...
玩转 Scrapy 框架 (一):Scrapy 框架介绍及使用入门
目录 一、Scrapy 框架介绍二、Scrapy 入门 一、Scrapy 框架介绍 简介: Scrapy 是一个基于 Python 开发的爬虫框架,可以说它是当前 Python 爬虫生态中最流行的爬虫框架,该框架提供了非常多爬虫的相关组件,架构清晰,可扩…...
node.js mongoose index(索引)
目录 简介 索引类型 单索引 复合索引 文本索引 简介 在 Mongoose 中,索引(Index)是一种用于提高查询性能的数据结构,它可以加速对数据库中文档的检索操作 索引类型 单索引、复合索引、文本索引、多键索引、哈希索引、地理…...
谷歌推大语言模型VideoPoet:文本图片皆可生成视频和音频
Google Research最近发布了一款名为VideoPoet的大型语言模型(LLM),旨在解决当前视频生成领域的挑战。该领域近年来涌现出许多视频生成模型,但在生成连贯的大运动时仍存在瓶颈。现有领先模型要么生成较小的运动,要么在生…...
ES-mapping
类似数据库中的表结构定义,主要作用如下 定义Index下的字段名( Field Name) 定义字段的类型,比如数值型、字符串型、布尔型等定义倒排索引相关的配置,比如是否索引、记录 position 等 index_options 用于控制倒排索记录的内容,有如…...
Centos 7.9安装Oracle19c步骤亲测可用有视频
视频介绍了在虚拟机安装centos 7.9并安装数据库软件的全过程 视频链接:https://www.zhihu.com/zvideo/1721267375351996416 下面的文字描述是安装数据库的部分介绍 一.安装环境准备 链接:https://pan.baidu.com/s/1Ogn47UZQ2w7iiHAiVdWDSQ 提取码&am…...
.NET中的Swagger使用
目录 前言 一、Swagger是什么? 二、如何Swagger文档说明的信息 1.在AddSwaggerGen方法中写入文档信息 2.运行效果 二、文档UI界面标题、路由设置 1.在中间件UseSwaggerUI方法中配置 三、文档UI界面添加接口注释 1.在 .csproj中配置 2.在AddSwaggerGen方法中配置Incl…...
结构屈曲分析
结构屈曲分析主要用于判定结构受载后是否有失稳风险,作为工程应用,一般分为线性屈曲分析和非线性屈曲分析。 线性屈曲分析需要具备较多的前提条件,如载荷无偏心、材料无缺陷等,在实际工程应用中结构制作过程和加载方式很难达到线性…...
Flink 客户端操作命令及可视化工具
Flink提供了丰富的客户端操作来提交任务和与任务进行交互。下面主要从Flink命令行、Scala Shell、SQL Client、Restful API和 Web五个方面进行整理。 在Flink安装目录的bin目录下可以看到flink,start-scala-shell.sh和sql-client.sh等文件,这些都是客户…...
csrf自动化检测调研
https://github.com/pillarjs/understanding-csrf/blob/master/README_zh.md CSRF 攻击者在钓鱼站点,可以通过创建一个AJAX按钮或者表单来针对你的网站创建一个请求: <form action"https://my.site.com/me/something-destructive" metho…...
记录一个Python鼠标自动模块用法和selenium加载网页插件的设置
写爬虫,或者网页自动化,让程序自动完成一些重复性的枯燥的网页操作,是最常见的需求。能够解放双手,空出时间看看手机,或者学习别的东西,甚至还能帮朋友亲戚减轻工作量。 然而,网页自动化代码编写…...
【数据库系统概论】第3章-关系数据库标准语言SQL(1)
文章目录 3.1 SQL概述3.2 学生-课程数据库3.3 数据定义3.3.1 数据库定义3.3.2 模式的定义3.3.3 基本表的定义3.3.4 索引的建立与删除3.3.5 数据字典 3.1 SQL概述 动词 分类 三级模式 3.2 学生-课程数据库 3.3 数据定义 3.3.1 数据库定义 创建数据库 tips:[ ]表…...
【Python】基于flaskMVT架构与session实现博客前台登录登出功能
目录 一、MVT说明 1.Model层 2.View层 3.Template层 二、功能说明 三、代码框架展示 四、具体代码实现 models.py 登录界面前端代码 博客界面前端代码(profile.html) main.py 一、MVT说明 MVT架构是Model-View-Template的缩写,是…...
为什么有的开关电源需要加自举电容?
一、什么是自举电路? 1.1 自举的概念 首先,自举电路也叫升压电路,是利用自举升压二极管,自举升压电容等电子元件,使电容放电电压和电源电压叠加,从而使电压升高。有的电路升高的电压能达到数倍电源电压。…...
【MCAL】TC397+EB-treso之MCU配置实战 - 芯片时钟
本篇文章介绍了在TC397平台使用EB-treso对MCU驱动模块进行配置的实战过程,主要介绍了后续基本每个外设模块都要涉及的芯片时钟部分,帮助读者了解TC397芯片的时钟树结构,在后续计算配置不同外设模块诸如通信速率,定时器周期等&…...
高级人工智能之群体智能:蚁群算法
群体智能 鸟群: 鱼群: 1.基本介绍 蚁群算法(Ant Colony Optimization, ACO)是一种模拟自然界蚂蚁觅食行为的优化算法。它通常用于解决路径优化问题,如旅行商问题(TSP)。 蚁群算法的基本步骤…...
【SpringBoot应用篇】【AOP+注解】SpringBoot+SpEL表达式基于注解实现权限控制
【SpringBoot应用篇】【AOP注解】SpringBootSpEL表达式基于注解实现权限控制 Spring SpEL基本表达式类相关表达式表达式模板 SpEL表达式实现权限控制PreAuthAuthFunPreAuthAspectUserControllerSpelParserUtils Spring SpEL Spring 表达式语言 SpEL 是一种非常强大的表达式语言…...
Java研学-HTTP 协议
一 概述 1 概念和作用 概念:HTTP 是 HyperText Transfer Protocol (超文本传输协议)的简写,它是 TCP/IP 协议之上的一个应用层协议。简单理解就是 HTTP 协议底层是对 TCP/IP 协议的封装。 作用:用于规定浏览器和服务器之间数据传输的格式…...
差生文具多之(二): perf
栈回溯和符号解析是使用 perf 的两大阻力,本文以应用程序 fio 的观测为例子,提供一些处理它们的经验法则,希望帮助大家无痛使用 perf。 前言 系统级性能优化通常包括两个阶段:性能剖析和代码优化: 性能剖析的目标是寻…...