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

剑指offer题解合集——Week7day1[滑动窗口的最大值]

滑动窗口的最大值

题目描述

给定一个数组和滑动窗口的大小,请找出所有滑动窗口里的最大值。

例如,如果输入数组 [2,3,4,2,6,2,5,1]
及滑动窗口的大小 3
,那么一共存在 6
个滑动窗口,它们的最大值分别为 [4,4,6,6,6,5]

注意:
数据保证 k大于 0,且 k小于等于数组长度。
数据范围
数组长度 [1,1000]

样例
输入:[2, 3, 4, 2, 6, 2, 5, 1] , k=3
输出: [4, 4, 6, 6, 6, 5]

思路

模拟窗口的滑动
当窗口里有k个元素的时候, 向后滑动

  • 检查窗口内元素是否合法
  • 窗口的一端纳入一个元素
  • 窗口的另一端移除一个元素

由于符合先进先出的原则,所以可以用队列来模拟窗口
然后进一步挖掘性质:

假设公司里有一群员工, 现在来了一个新员工A, 如果员工A的能力出众, 并且年纪小, 那么

  1. A可以替换掉所有员工中能力小于等于A的员工
  2. A可以替换掉所有员工中年龄小于等于A的员工

能力->本题的数值
年龄->本题的索引

那么:

  1. 为什么上面的性质合理呢?
    因为滑动窗口需要的是最大值,所以,只要当前元素大于队列中元素,那么队列中元素就不需要了
  2. 为什么可以取等?
    因为两个数值一样的元素并列, 例如int a[3] = {1, 1, 1};, a数组里三个元素均相等,那么当需要最大值的时候
    取a[2]一定没错, 因为如果返回a[0], 那么窗口移动以后,a[0]会被移除,a[1]同理

也就是说,a[2]活到了最后

所以:
最终队列会形成一个递减序列, 因此, 队头元素就是最大值
每次从队头里获取最大值,放入到结果数组中

代码

class Solution {
public:vector<int> maxInWindows(vector<int>& nums, int k) {vector<int> res;deque<int> q;for (int i = 0; i < nums.size(); i ++ ){if (q.size() && i - q.front() >= k) q.pop_front();while (q.size() && nums[q.back()] <= nums[i]) q.pop_back();q.push_back(i);if (i >= k - 1) res.push_back(nums[q.front()]);}return res;}
};

相关文章:

剑指offer题解合集——Week7day1[滑动窗口的最大值]

滑动窗口的最大值 题目描述 给定一个数组和滑动窗口的大小&#xff0c;请找出所有滑动窗口里的最大值。 例如&#xff0c;如果输入数组 [2,3,4,2,6,2,5,1] 及滑动窗口的大小 3 &#xff0c;那么一共存在 6 个滑动窗口&#xff0c;它们的最大值分别为 [4,4,6,6,6,5] 注意&am…...

深入解读财报,开启美股投资之旅

投资股票市场&#xff0c;尤其是美股市场&#xff0c;对于许多投资者来说是一项充满挑战的活动。然而&#xff0c;无论投资者是倾向于技术分析还是基本面分析&#xff0c;财报都是他们不可或缺的工具。本文将带领读者深入了解如何通过阅读和分析财报&#xff0c;发现潜在的投资…...

邦芒支招:成功找到工作要掌握的3个知识点

社会进步&#xff0c;企业商业竞争越来越激烈&#xff0c;不管身为一名职场小白或是想调换一下目前的工作的人&#xff0c;都想找到一个称心如意的好工作。拥有以下三点知识点&#xff0c;可以使我们找到工作。 1、迫不得已&#xff0c;别做这件事 拍桌子说“我不开了”的时候有…...

Educational Codeforces Round 168 (Rated for Div. 2)-7.30复盘

A. Strong Password 简单题&#xff0c;找到相同的两个相邻字母之间插一个跟他们不同的大写字母即可 inline void solve(){cin>>s;int id0;char hh ;for(int i1;i<s.size();i){if(s[i-1]s[i]){idi;break;}} for(int i0;i<26;i){if(s[id]!ai&&s[id1]!ai) …...

Web开发:小结Apache Echarts官网上常用的配置项(前端可视化图表)

目录 一、须知 二、Title 三、 Legend 四、Grid 一、须知 配置项官方文档&#xff1a;点此进入。 我总结了比较常用的功能&#xff0c;写进注释里面&#xff0c;附带链接分享和效果图展示。&#xff08;更新中....&#xff09; 二、Title option {title: {text: Weekl…...

B树的平衡性与性能优化

B树的平衡性与性能优化 B树&#xff08;B-tree&#xff09;是一种自平衡的树数据结构&#xff0c;广泛应用于数据库和文件系统中&#xff0c;用于保持数据的有序性并允许高效的插入、删除和查找操作。B树能够很好地处理大规模数据&#xff0c;并在磁盘I/O操作中表现出色。本文…...

llama3源码解读之推理-infer

文章目录 前言一、整体源码解读1、完整main源码2、tokenizer加载3、llama3模型加载4、llama3测试数据文本加载5、llama3模型推理模块1、模型推理模块的数据处理2、模型推理模块的model.generate预测3、模型推理模块的预测结果处理6、多轮对话二、llama3推理数据处理1、完整数据…...

【教程】Linux安装Redis步骤记录

下载地址 Index of /releases/ Downloads - Redis 安装redis-7.4.0.tar.gz 1.下载安装包 wget https://download.redis.io/releases/redis-7.4.0.tar.gz 2.解压 tar -zxvf redis-7.4.0.tar.gz 3.进入目录 cd redis-7.4.0/ 4.编译 make 5.安装 make install PREFIX/u…...

全球汽车线控制动系统市场规模预测:未来六年CAGR为17.3%

引言&#xff1a; 随着汽车行业的持续发展和对安全性能需求的增加&#xff0c;汽车线控制动系统作为提升车辆安全性和操控性的关键组件&#xff0c;正逐渐受到市场的广泛关注。本文旨在通过深度分析汽车线控制动系统行业的各个维度&#xff0c;揭示行业发展趋势和潜在机会。 【…...

Ubuntu运行深度学习代码,代码随机epoch中断没有任何报错

深度学习运行代码直接中断 文章目录 深度学习运行代码直接中断问题描述设备信息问题补充解决思路问题发现及正确解决思路新问题出现最终问题&#xff1a;ubuntu系统&#xff0c;4090显卡安装英伟达驱动535.x外的驱动会导致开机无法进入桌面问题记录 问题描述 运行深度学习代码…...

只有4%知道的Linux,看了你也能上手Ubuntu桌面系统,Ubuntu简易设置,源更新,root密码,远程服务...

创作不易 只因热爱!! 热衷分享&#xff0c;一起成长! “你的鼓励就是我努力付出的动力” 最近常提的一句话&#xff0c;那就是“但行好事&#xff0c;莫问前程"! 与辉同行的董工说​&#xff1a;​守正出奇。坚持分享&#xff0c;坚持付出&#xff0c;坚持奉献&#xff0c…...

Tomcat部署——个人笔记

Tomcat部署——个人笔记 文章目录 [toc]简介安装配置文件WEB项目的标准结构WEB项目部署IDEA中开发并部署运行WEB项目 本学习笔记参考尚硅谷等教程。 简介 Apache Tomcat 官网 Tomcat是Apache 软件基金会&#xff08;Apache Software Foundation&#xff09;的Jakarta 项目中…...

常见且重要的用户体验原则

以下是一些常见且重要的用户体验原则&#xff1a; 1. 以用户为中心 - 深入了解用户的需求、期望、目标和行为习惯。通过用户研究、调查、访谈等方法获取真实的用户反馈&#xff0c;以此来设计产品或服务。 - 例如&#xff0c;在设计一款老年手机时&#xff0c;充分考虑老年…...

web基础及nginx搭建

第四周 上午 静态资源 根据开发者保存在项目资源目录中的路径访问静态资源 html 图片 js css 音乐 视频 f12 &#xff0c;开发者工具&#xff0c;网络 1 、 web 基本概念 web 服务器&#xff08; web server &#xff09;&#xff1a;也称 HTTP 服务器&#xff08; HTTP …...

C++ 布隆过滤器

1. 布隆过滤器提出 我们在使用新闻客户端看新闻时&#xff0c;它会给我们不停地推荐新的内容&#xff0c;它每次推荐时要去重&#xff0c;去掉 那些已经看过的内容。问题来了&#xff0c;新闻客户端推荐系统如何实现推送去重的&#xff1f; 用服务器记录了用 户看过的所有历史…...

使用HTML创建用户注册表单

在当今数字化时代&#xff0c;网页表单对于收集用户信息和促进网站交互至关重要。无论您设计简单的注册表单还是复杂的调查表&#xff0c;了解HTML的基础知识可以帮助您构建有效的用户界面。在本教程中&#xff0c;我们将详细介绍如何使用HTML创建基本的用户注册表单。 第一步…...

Python零基础入门教程

Python零基础详细入门教程可以从以下几个方面进行学习和掌握&#xff1a; 一、Python基础认知 1. Python简介 由来与发展&#xff1a;Python是一种广泛使用的高级编程语言&#xff0c;由Guido van Rossum&#xff08;吉多范罗苏姆&#xff09;于1991年首次发布。Python以其简…...

成为git砖家(10): 根据文件内容生成SHA-1

文章目录 1. .git/objects 目录2. git cat-file 命令3. 根据文件内容生成 sha-14. 结语5. References 1. .git/objects 目录 git 是一个根据文件内容进行检索的系统。 当创建 hello.py, 填入 print("hello, world")的内容&#xff0c; 并执行 git add hello.py gi…...

园区导航小程序:一站式解决园区导航问题,释放存储,优化访客体验

随着园区的规模不断扩大&#xff0c;功能区划分日益复杂&#xff0c;导致访客和新员工在没有有效导航的情况下容易迷路。传统APP导航虽能解决部分问题&#xff0c;但其下载安装繁琐、占用手机内存大、且非高频使用导致的闲置&#xff0c;让许多用户望而却步。园区导航小程序的出…...

对于n进制转十进制的解法及代码(干货!)

对于p进制转十进制&#xff0c;我们有&#xff1a;(x)pa[0]*p^0a[1]*p^1a[2]*p^2...a[n]*p^n 举个例子&#xff1a;&#xff08;11001&#xff09;21*10*20*41*81*1625 &#xff08;9FA&#xff09;1610*16^015*16^19*16^22554 据此&#xff0c;我们可以编出c代码来解决问题 …...

在鸿蒙HarmonyOS 5中实现抖音风格的点赞功能

下面我将详细介绍如何使用HarmonyOS SDK在HarmonyOS 5中实现类似抖音的点赞功能&#xff0c;包括动画效果、数据同步和交互优化。 1. 基础点赞功能实现 1.1 创建数据模型 // VideoModel.ets export class VideoModel {id: string "";title: string ""…...

练习(含atoi的模拟实现,自定义类型等练习)

一、结构体大小的计算及位段 &#xff08;结构体大小计算及位段 详解请看&#xff1a;自定义类型&#xff1a;结构体进阶-CSDN博客&#xff09; 1.在32位系统环境&#xff0c;编译选项为4字节对齐&#xff0c;那么sizeof(A)和sizeof(B)是多少&#xff1f; #pragma pack(4)st…...

1.3 VSCode安装与环境配置

进入网址Visual Studio Code - Code Editing. Redefined下载.deb文件&#xff0c;然后打开终端&#xff0c;进入下载文件夹&#xff0c;键入命令 sudo dpkg -i code_1.100.3-1748872405_amd64.deb 在终端键入命令code即启动vscode 需要安装插件列表 1.Chinese简化 2.ros …...

相机从app启动流程

一、流程框架图 二、具体流程分析 1、得到cameralist和对应的静态信息 目录如下: 重点代码分析: 启动相机前,先要通过getCameraIdList获取camera的个数以及id,然后可以通过getCameraCharacteristics获取对应id camera的capabilities(静态信息)进行一些openCamera前的…...

用机器学习破解新能源领域的“弃风”难题

音乐发烧友深有体会&#xff0c;玩音乐的本质就是玩电网。火电声音偏暖&#xff0c;水电偏冷&#xff0c;风电偏空旷。至于太阳能发的电&#xff0c;则略显朦胧和单薄。 不知你是否有感觉&#xff0c;近两年家里的音响声音越来越冷&#xff0c;听起来越来越单薄&#xff1f; —…...

算法岗面试经验分享-大模型篇

文章目录 A 基础语言模型A.1 TransformerA.2 Bert B 大语言模型结构B.1 GPTB.2 LLamaB.3 ChatGLMB.4 Qwen C 大语言模型微调C.1 Fine-tuningC.2 Adapter-tuningC.3 Prefix-tuningC.4 P-tuningC.5 LoRA A 基础语言模型 A.1 Transformer &#xff08;1&#xff09;资源 论文&a…...

【Redis】笔记|第8节|大厂高并发缓存架构实战与优化

缓存架构 代码结构 代码详情 功能点&#xff1a; 多级缓存&#xff0c;先查本地缓存&#xff0c;再查Redis&#xff0c;最后才查数据库热点数据重建逻辑使用分布式锁&#xff0c;二次查询更新缓存采用读写锁提升性能采用Redis的发布订阅机制通知所有实例更新本地缓存适用读多…...

【学习笔记】erase 删除顺序迭代器后迭代器失效的解决方案

目录 使用 erase 返回值继续迭代使用索引进行遍历 我们知道类似 vector 的顺序迭代器被删除后&#xff0c;迭代器会失效&#xff0c;因为顺序迭代器在内存中是连续存储的&#xff0c;元素删除后&#xff0c;后续元素会前移。 但一些场景中&#xff0c;我们又需要在执行删除操作…...

c++第七天 继承与派生2

这一篇文章主要内容是 派生类构造函数与析构函数 在派生类中重写基类成员 以及多继承 第一部分&#xff1a;派生类构造函数与析构函数 当创建一个派生类对象时&#xff0c;基类成员是如何初始化的&#xff1f; 1.当派生类对象创建的时候&#xff0c;基类成员的初始化顺序 …...

【LeetCode】算法详解#6 ---除自身以外数组的乘积

1.题目介绍 给定一个整数数组 nums&#xff0c;返回 数组 answer &#xff0c;其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。 题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。 请 不要使用除法&#xff0c;且在 O…...