当前位置: 首页 > 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代码来解决问题 …...

阿里云ACP云计算备考笔记 (5)——弹性伸缩

目录 第一章 概述 第二章 弹性伸缩简介 1、弹性伸缩 2、垂直伸缩 3、优势 4、应用场景 ① 无规律的业务量波动 ② 有规律的业务量波动 ③ 无明显业务量波动 ④ 混合型业务 ⑤ 消息通知 ⑥ 生命周期挂钩 ⑦ 自定义方式 ⑧ 滚的升级 5、使用限制 第三章 主要定义 …...

macOS多出来了:Google云端硬盘、YouTube、表格、幻灯片、Gmail、Google文档等应用

文章目录 问题现象问题原因解决办法 问题现象 macOS启动台&#xff08;Launchpad&#xff09;多出来了&#xff1a;Google云端硬盘、YouTube、表格、幻灯片、Gmail、Google文档等应用。 问题原因 很明显&#xff0c;都是Google家的办公全家桶。这些应用并不是通过独立安装的…...

leetcodeSQL解题:3564. 季节性销售分析

leetcodeSQL解题&#xff1a;3564. 季节性销售分析 题目&#xff1a; 表&#xff1a;sales ---------------------- | Column Name | Type | ---------------------- | sale_id | int | | product_id | int | | sale_date | date | | quantity | int | | price | decimal | -…...

Swagger和OpenApi的前世今生

Swagger与OpenAPI的关系演进是API标准化进程中的重要篇章&#xff0c;二者共同塑造了现代RESTful API的开发范式。 本期就扒一扒其技术演进的关键节点与核心逻辑&#xff1a; &#x1f504; 一、起源与初创期&#xff1a;Swagger的诞生&#xff08;2010-2014&#xff09; 核心…...

CRMEB 中 PHP 短信扩展开发:涵盖一号通、阿里云、腾讯云、创蓝

目前已有一号通短信、阿里云短信、腾讯云短信扩展 扩展入口文件 文件目录 crmeb\services\sms\Sms.php 默认驱动类型为&#xff1a;一号通 namespace crmeb\services\sms;use crmeb\basic\BaseManager; use crmeb\services\AccessTokenServeService; use crmeb\services\sms\…...

Webpack性能优化:构建速度与体积优化策略

一、构建速度优化 1、​​升级Webpack和Node.js​​ ​​优化效果​​&#xff1a;Webpack 4比Webpack 3构建时间降低60%-98%。​​原因​​&#xff1a; V8引擎优化&#xff08;for of替代forEach、Map/Set替代Object&#xff09;。默认使用更快的md4哈希算法。AST直接从Loa…...

基于PHP的连锁酒店管理系统

有需要请加文章底部Q哦 可远程调试 基于PHP的连锁酒店管理系统 一 介绍 连锁酒店管理系统基于原生PHP开发&#xff0c;数据库mysql&#xff0c;前端bootstrap。系统角色分为用户和管理员。 技术栈 phpmysqlbootstrapphpstudyvscode 二 功能 用户 1 注册/登录/注销 2 个人中…...

LOOI机器人的技术实现解析:从手势识别到边缘检测

LOOI机器人作为一款创新的AI硬件产品&#xff0c;通过将智能手机转变为具有情感交互能力的桌面机器人&#xff0c;展示了前沿AI技术与传统硬件设计的完美结合。作为AI与玩具领域的专家&#xff0c;我将全面解析LOOI的技术实现架构&#xff0c;特别是其手势识别、物体识别和环境…...

Android写一个捕获全局异常的工具类

项目开发和实际运行过程中难免会遇到异常发生&#xff0c;系统提供了一个可以捕获全局异常的工具Uncaughtexceptionhandler&#xff0c;它是Thread的子类&#xff08;就是package java.lang;里线程的Thread&#xff09;。本文将利用它将设备信息、报错信息以及错误的发生时间都…...

ArcPy扩展模块的使用(3)

管理工程项目 arcpy.mp模块允许用户管理布局、地图、报表、文件夹连接、视图等工程项目。例如&#xff0c;可以更新、修复或替换图层数据源&#xff0c;修改图层的符号系统&#xff0c;甚至自动在线执行共享要托管在组织中的工程项。 以下代码展示了如何更新图层的数据源&…...