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

剑指 Offer 59 - I. 滑动窗口的最大值 / LeetCode 239. 滑动窗口最大值(优先队列 / 单调队列)

题目:

链接:剑指 Offer 59 - I. 滑动窗口的最大值;LeetCode 239. 滑动窗口最大值
难度:困难
下一篇:剑指 Offer 59 - II. 队列的最大值(单调队列)

给你一个整数数组 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    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

示例 2:

输入:nums = [1], k = 1
输出:[1]

提示:

  • 1 <= nums.length <= 105
  • -104 <= nums[i] <= 104
  • 1 <= k <= nums.length

方法一:

优先队列(不推荐):

优先队列的本质是最大堆,可以帮助实时维护一个滑动窗口中的最大值。
初始时,将数组nums前k个元素插入优先队列中。每当右移窗口时,就将新的元素插入优先队列(最大堆),那么此时堆顶的元素就是最大值。然而这个最大值有可能经过右移已不在窗口中(在窗口左边界的更左位置),所以我们要根据这个栈顶元素的实际坐标移除已不在窗口中的堆顶元素,直到堆顶元素确实在窗口范围中,此时的堆顶元素才是窗口内的最大值。
为了方便判断堆顶元素与滑动窗口的位置关系,我们可以在优先队列中存储二元组 (num,index),表示元素 num 在数组中的下标为 index。优先队列会默认按第一个整数进行优先级排序。

代码一:

class Solution {
public:vector<int> maxSlidingWindow(vector<int>& nums, int k) {int n = nums.size();if(n == 0) return {};priority_queue<pair<int, int>> window;  // 维护一个滑动窗口内的优先队列vector<int> ans;for(int i = 0; i < k; i++){window.emplace(nums[i], i);}ans.emplace_back(window.top().first);for(int i = k; i < n; i++){window.emplace(nums[i], i);while(window.top().second <= i - k) {  // 将滑动窗口外的元素删掉window.pop();}ans.emplace_back(window.top().first);}return ans;}
};

时间复杂度O(NlogN)。在最坏情况下,nums数组呈单调递增,优先队列中插入了所有元素且没有元素被删除,将一个元素插入优先队列的时间复杂度为O(logN),n个元素为O(NlogN)。
空间复杂度O(N)。在上述的最坏情况下,优先队列需要n个元素的空间。

方法二:

单调队列(推荐):

使用双端队列deque实现的单调队列详解看单调队列结构解决滑动窗口问题。
顺着方法一的思路进行优化,方法一中优先队列在发现堆顶元素在窗口外之前仍保留窗口外元素的特点是冗余的。我们可以发现,若滑动窗口中有两个下标 i < j,nums[i] <= nums[j],只要 i 还在窗口中,j 一定也在窗口中,nums[i] 就一定不是窗口最大值了,所以 nums[i] 可以被永久移除。这符合单调队列的性质。

代码二:

class Solution {
public:vector<int> maxSlidingWindow(vector<int>& nums, int k) {int n = nums.size();if(n == 0) return {};deque<int> window;  //单调递减队列vector<int> ans;for(int i = 0; i < n; i++){while(!window.empty() && window.back() < nums[i]) {  //维护一个单调递减队列,把单调队列中比新元素小的元素全部删除window.pop_back();}window.emplace_back(nums[i]);if(i == k - 1) {ans.emplace_back(window.front());}else if(i >= k) {if(window.front() == nums[i - k]) window.pop_front();  //维护一个单调递减队列,删除滑动窗口右移丢失的最大值ans.emplace_back(window.front());}}return ans;}
};

时间复杂度O(N)。
空间复杂度O(k)。窗口右移时从队首弹出元素保证了队列内不会有超过 k+1 个元素。

相关文章:

剑指 Offer 59 - I. 滑动窗口的最大值 / LeetCode 239. 滑动窗口最大值(优先队列 / 单调队列)

题目&#xff1a; 链接&#xff1a;剑指 Offer 59 - I. 滑动窗口的最大值&#xff1b;LeetCode 239. 滑动窗口最大值 难度&#xff1a;困难 下一篇&#xff1a;剑指 Offer 59 - II. 队列的最大值&#xff08;单调队列&#xff09; 给你一个整数数组 nums&#xff0c;有一个大…...

【Linux后端服务器开发】IP协议

目录 一、IP协议概述 二、协议头格式 三、网段划分 四、IP地址的数量限制 五、路由 六、分片和组装 一、IP协议概述 主机&#xff1a;配有IP地址&#xff0c;但是不进行路由控制的设备 路由器&#xff1a;即配有IP地址&#xff0c;又能进行路由控制 节点&#xff1a;主…...

React组件进阶之children属性,props校验与默认值以及静态属性static

React组件进阶之children属性,props校验与默认值以及静态属性static 一、children属性二、props校验2.1 props说明2.2 prop-types的安装2.3 props校验规则2.4 props默认值 三、静态属性static 一、children属性 children 属性&#xff1a;表示该组件的子节点&#xff0c;只要组…...

ceph集群中RBD的性能测试、性能调优

文章目录 rados benchrbd bench-write测试工具Fio测试ceph rbd块设备的iops性能测试ceph rbd块设备的带宽测试ceph rbd块设备的延迟 性能调优 rados bench 参考&#xff1a;https://blog.csdn.net/Micha_Lu/article/details/126490260 rados bench为ceph自带的基准测试工具&am…...

texshop mac中文版-TeXShop for Mac(Latex编辑预览工具)

texshop for mac是一款可以在苹果电脑MAC OS平台上使用的非常不错的Mac应用软件&#xff0c;texshop for mac是一个非常有用的工具&#xff0c;广泛使用在数学&#xff0c;计算机科学&#xff0c;物理学&#xff0c;经济学等领域的合作&#xff0c;这些程序的标准tetex分布特产…...

简单认识redis高可用实现方法

文章目录 一、redis群集三种模式二、 Redis 主从复制1、简介2、作用&#xff1a;3、流程&#xff1a;4.配置主从复制 三、Redis 哨兵模式1、简介2、原理:3、作用&#xff1a;4、哨兵结构由两部分组成&#xff0c;哨兵节点和数据节点&#xff1a;5、故障转移机制&#xff1a;6、…...

搭建git服务器

1.创建linux账户&#xff0c;创建文件 adduser git passwd gitpsw su git pwd cd ~/ mkdir .ssh cd ~/.ssh touch authorized_keys 2.特别重要(单独起一行)&#xff0c;给文件设权限 chmod 700 /home/git/.ssh chmod 600 /home/git/.ssh/authorized_keys 3.本地生产密钥并把…...

线程中断机制

如何中断一个线程&#xff1f; 首先一个线程不应该由其他线程来强制中断或者停止&#xff0c;而是应该由线程自己自行停止。所以我们看到线程的stop()、resume()、suspend()等方法已经被标记为过时了。 其次在java中没有办法立即停止一个线程&#xff0c;然而停止线程显得尤为重…...

CollectionUtils工具类的使用

来自&#xff1a;小小程序员。 本文仅作记录 org.apache.commons.collections包下的CollectionUtils工具类&#xff0c;下面说说它的用法&#xff1a; 一、集合判空 通过CollectionUtils工具类的isEmpty方法可以轻松判断集合是否为空&#xff0c;isNotEmpty方法判断集合不为…...

基于Nonconvex规划的配电网重构研究(Matlab代码实现)

&#x1f4a5;&#x1f4a5;&#x1f49e;&#x1f49e;欢迎来到本博客❤️❤️&#x1f4a5;&#x1f4a5; &#x1f3c6;博主优势&#xff1a;&#x1f31e;&#x1f31e;&#x1f31e;博客内容尽量做到思维缜密&#xff0c;逻辑清晰&#xff0c;为了方便读者。 ⛳️座右铭&a…...

yolo系列笔记(v4-v5)

YOLOv4 YOLOv4网络详解_哔哩哔哩_bilibili 网络结构&#xff0c;在Yolov3的Darknet的基础上增加了CSP结构。 CSP的优点&#xff1a; 加强CNN的学习能力 去除计算瓶颈。 减少显存的消耗。 结构为&#xff1a; 、 其实还是类似与残差网络的结构&#xff0c;保留下采样之前…...

小白如何高效刷题Leetcode?

文章目录 为什么会有这样的现象&#xff1f;研究与学习人生而有别 如何解决困境&#xff1f;1. 要补的&#xff1a;化抽象为具体&#xff0c;列举找规律2. 要补的&#xff1a;前人总结的套路3. 与人交流探讨4. 多写总结文章 总结 明明自觉学会了不少知识&#xff0c;可真正开始…...

使用IDEA打jar包的详细图文教程

1. 点击intellij idea左上角的“File”菜单 -> Project Structure 2. 点击"Artifacts" -> 绿色的"" -> “JAR” -> Empty 3. Name栏填入自定义的名字&#xff0c;Output ditectory 选择 jar 包目标目录&#xff0c;Available Elements 里右击…...

《MySQL 实战 45 讲》课程学习笔记(二)

日志系统&#xff1a;一条 SQL 更新语句是如何执行的&#xff1f; 与查询流程不一样的是&#xff0c;更新流程还涉及两个重要的日志模块&#xff1a;redo log&#xff08;重做日志&#xff09;和 binlog&#xff08;归档日志&#xff09;。 重要的日志模块&#xff1a;redo l…...

微软亚研院提出模型基础架构RetNet或将成为Transformer有力继承者

作为全新的神经网络架构&#xff0c;RetNet 同时实现了良好的扩展结果、并行训练、低成本部署和高效推理。这些特性将使 RetNet 有可能成为继 Transformer 之后大语言模型基础网络架构的有力继承者。实验数据也显示&#xff0c;在语言建模任务上&#xff1a; RetNet 可以达到与…...

探索单例模式:设计模式中的瑰宝

文章目录 常用的设计模式有以下几种&#xff1a;一.创建型模式&#xff08;Creational Patterns&#xff09;&#xff1a;二.结构型模式&#xff08;Structural Patterns&#xff09;&#xff1a;三.行为型模式&#xff08;Behavioral Patterns&#xff09;&#xff1a;四.并发…...

Bobo String Construction 2023牛客暑期多校训练营4-A

登录—专业IT笔试面试备考平台_牛客网 题目大意&#xff1a;给出一字符串t&#xff0c;求一个长为n的字符串&#xff0c;使tst中包含且仅包含两个t 1<n<1000;测试样例组数<1000 思路&#xff1a;一开始很容易想到如果t里有1&#xff0c;s就全0&#xff0c;否则s就全…...

【React学习】React父子组件通讯

1. 父到子传值 在React框架中&#xff0c;父组件可以通过 props 将数据传递给子组件。子组件通过读取 props 来访问父组件传递过来的数据。 当父组件的 props 发生变化时&#xff0c;React 会自动重新渲染子组件以确保子组件中使用的数据保持同步。 父组件 import React, {…...

NASM汇编

1. 前置知识 1. 汇编语言两种风格 intel&#xff1a;我们学的NASM就属于Intel风格AT&T&#xff1a;GCC后端工具默认使用这种风格&#xff0c;当然我们也可以加选项改成intel风格 2. 代码 1. 段分布 .text: 存放的是二进制机器码&#xff0c;只读.data: 存放有初始化的…...

第三章 HL7 架构和可用工具 - 使用 HL7 架构结构页面

文章目录 第三章 HL7 架构和可用工具 - 使用 HL7 架构结构页面使用 HL7 架构结构页面查看文档类型列表查看消息结构查看段结构 第三章 HL7 架构和可用工具 - 使用 HL7 架构结构页面 使用 HL7 架构结构页面 通过 HL7 架构页面&#xff0c;可以导入和查看 HL7 版本 2 架构规范。…...

SkyWalking 10.2.0 SWCK 配置过程

SkyWalking 10.2.0 & SWCK 配置过程 skywalking oap-server & ui 使用Docker安装在K8S集群以外&#xff0c;K8S集群中的微服务使用initContainer按命名空间将skywalking-java-agent注入到业务容器中。 SWCK有整套的解决方案&#xff0c;全安装在K8S群集中。 具体可参…...

ES6从入门到精通:前言

ES6简介 ES6&#xff08;ECMAScript 2015&#xff09;是JavaScript语言的重大更新&#xff0c;引入了许多新特性&#xff0c;包括语法糖、新数据类型、模块化支持等&#xff0c;显著提升了开发效率和代码可维护性。 核心知识点概览 变量声明 let 和 const 取代 var&#xf…...

DBAPI如何优雅的获取单条数据

API如何优雅的获取单条数据 案例一 对于查询类API&#xff0c;查询的是单条数据&#xff0c;比如根据主键ID查询用户信息&#xff0c;sql如下&#xff1a; select id, name, age from user where id #{id}API默认返回的数据格式是多条的&#xff0c;如下&#xff1a; {&qu…...

Matlab | matlab常用命令总结

常用命令 一、 基础操作与环境二、 矩阵与数组操作(核心)三、 绘图与可视化四、 编程与控制流五、 符号计算 (Symbolic Math Toolbox)六、 文件与数据 I/O七、 常用函数类别重要提示这是一份 MATLAB 常用命令和功能的总结,涵盖了基础操作、矩阵运算、绘图、编程和文件处理等…...

【学习笔记】深入理解Java虚拟机学习笔记——第4章 虚拟机性能监控,故障处理工具

第2章 虚拟机性能监控&#xff0c;故障处理工具 4.1 概述 略 4.2 基础故障处理工具 4.2.1 jps:虚拟机进程状况工具 命令&#xff1a;jps [options] [hostid] 功能&#xff1a;本地虚拟机进程显示进程ID&#xff08;与ps相同&#xff09;&#xff0c;可同时显示主类&#x…...

【开发技术】.Net使用FFmpeg视频特定帧上绘制内容

目录 一、目的 二、解决方案 2.1 什么是FFmpeg 2.2 FFmpeg主要功能 2.3 使用Xabe.FFmpeg调用FFmpeg功能 2.4 使用 FFmpeg 的 drawbox 滤镜来绘制 ROI 三、总结 一、目的 当前市场上有很多目标检测智能识别的相关算法&#xff0c;当前调用一个医疗行业的AI识别算法后返回…...

10-Oracle 23 ai Vector Search 概述和参数

一、Oracle AI Vector Search 概述 企业和个人都在尝试各种AI&#xff0c;使用客户端或是内部自己搭建集成大模型的终端&#xff0c;加速与大型语言模型&#xff08;LLM&#xff09;的结合&#xff0c;同时使用检索增强生成&#xff08;Retrieval Augmented Generation &#…...

Android第十三次面试总结(四大 组件基础)

Activity生命周期和四大启动模式详解 一、Activity 生命周期 Activity 的生命周期由一系列回调方法组成&#xff0c;用于管理其创建、可见性、焦点和销毁过程。以下是核心方法及其调用时机&#xff1a; ​onCreate()​​ ​调用时机​&#xff1a;Activity 首次创建时调用。​…...

HashMap中的put方法执行流程(流程图)

1 put操作整体流程 HashMap 的 put 操作是其最核心的功能之一。在 JDK 1.8 及以后版本中&#xff0c;其主要逻辑封装在 putVal 这个内部方法中。整个过程大致如下&#xff1a; 初始判断与哈希计算&#xff1a; 首先&#xff0c;putVal 方法会检查当前的 table&#xff08;也就…...

iOS性能调优实战:借助克魔(KeyMob)与常用工具深度洞察App瓶颈

在日常iOS开发过程中&#xff0c;性能问题往往是最令人头疼的一类Bug。尤其是在App上线前的压测阶段或是处理用户反馈的高发期&#xff0c;开发者往往需要面对卡顿、崩溃、能耗异常、日志混乱等一系列问题。这些问题表面上看似偶发&#xff0c;但背后往往隐藏着系统资源调度不当…...