小白如何如何理解滑动窗口最大值问题python
文章目录
- 题目描述
- 思路
- 什么时候弹出元素
- 什么时候加入元素
- 代码示例和解释
题目描述
给你一个整数数组 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 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
思路
很容易想到暴力求解,遍历数据[i:i+k]取出max最大值即可,但是这种做法容易暴力超时,因此引出了自DIY的队列,主要关注的是什么时候弹出,什么时候加入队列
什么时候弹出元素
1.当遍历个数大于k的时候,弹出queue左侧==nums[i-k]
2.当队列最右侧元素小于nums[i],弹出右侧元素,因为他不可能是最大值了,队列内最多只有k个值,所以遍历到的这个元素才能成为最大值
什么时候加入元素
没遍历一次长度大于k的时候就加元素
代码示例和解释
from collections import deque
def max SlidingWindow(nums, k):queue = deque() # 双端都能插入删除的队列res = [] # 存放最后的结果# 把前面三个元素按需求加入到dequefor i in range(k):while queue and nums[i] > queue[-1]:queue.pop() # 弹出右边的元素,不可能成为最大值deque.append(nums[i])# 从k开始遍历后面的每个元素for i in range(k, len(nums)):# 只有遍历到的元素queue[0]等于nums[i-k]才需要弹出元素if queue and queue[0] == nums[i-k]:queue.popleft()while queue and queue[-1] < nums[i]:queue.pop()queue.append(nums[i])res.append(queue[0]) # 加入最大值return res
*[注意点]:queue内部的元素个数一定是小于等于k的,比如k = 3的时候,因为遍历到长度第4个元素,如果queue首元素和nums[i-k]元素相等就会有pop操作,即使不相等,其他需要pop()的元素也会被push的过程弹出,所以queue的长度始终不可能大于k
相关文章:
小白如何如何理解滑动窗口最大值问题python
文章目录 题目描述思路什么时候弹出元素什么时候加入元素 代码示例和解释 题目描述 给你一个整数数组 nums,有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。 举例: 输…...
Linux--进程间通信(2)(有名管道)
目录 1.原理 2.创建命名管道 3.使用命名通道实现简单的通信 4.使用创建的命名管道 1.原理 匿名管道没有名称,它们是通过句柄在父进程和子进程之间传递的。这意味着匿名管道只能用于具有父子关系的进程之间。 但如果程序之间没关系,那么这时候就要用…...
window自动启动bat文件
开机自动开启远程桌面, WinR 执行netplwiz 命令进入设置;取消勾选,可选择所需用户,点击应用,输入远程的密码即可 开机自动开启远程桌面, WinR 执行netplwiz 命令进入设置;取消勾选࿰…...
2024年蓝桥杯Web开发【大赛大纲】15届
一、 组别 Web应用开发分为:大学组和职业院校组。 每位选手只能申请参加其中一个组别的竞赛。各个组别单独评奖。 研究生和本科生只能报大学组。 其它高职高专院校可自行选择报任意组别。 二. 竞赛赛程 省赛时长:4小时。 决赛时长:4小…...
【vue-cli搭建vue项目的过程2.x】
vue-cli搭建vue项目 vue-cli搭建vue项目安装node安装vue-cli脚手架并创建项目安装 Ant Design Vue或element-ui(笔者使用Ant-design-vue组件,并全局引入)开发安装三方库包1、Package.json文件---引入如下package.json文件执行npm i或npm install命令即可下载如下依赖…...
Android 生成正式版密钥库 KeyStore
步骤1:打开生成正式版密钥库设置 点击 Build 菜单,选择 Generate Signed App Bundle or APK: 这是打开后的样子: 步骤2:选择 APK Android App Bundle 是用于上架 Google Play 商店的。 正常情况下选择 APK。 选择…...
POLARDB:新零售用户MySQL上云最佳选择
什么是云数据库POLARDB? POLARDB是阿里云自主研发的最新一代RDS关系型数据库,是特别针对互联网场景设计的Cloud-Native 云原生数据库。POLARDB for MySQL版本,在提供100%兼容MySQL5.6/8.0的关系型事务处理ACID特性之上,能够提供完…...
PHP MySQL图解学习指南:开启Web开发新篇章
PHP曾经是最流行的Web开发语言,许多世界领先的网站(如Facebook、维基百科和WordPress)都是用它编写的。PHP运行在Web服务器端,通过使用存储在MySQL数据库中的数据,使得网站可以为每一位访问者显示不同的定制页面。书中采用简单、直观的图示化…...
uniapp一些问题解决
1.按钮边框如何去除? 参考博主:微信小程序按钮去不掉边框_微信小程序button去掉边框-CSDN博客文章浏览阅读1k次。最近在学uni-app,顺便自己写个小程序。左上角放了个button,可边框怎么也去不掉…原来微信小程序的按钮要去掉边框要…...
数字经济讲师培训师教授唐兴通谈新质生产力数字化转型高质量发展AI人工智能大模型大数据经信委大数据管理局
什么是数字经济? 数字经济是指通过数字技术将个人、企业、设备、数据和运营连接起来而产生的经济活动。它涵盖了互联网、移动技术、大数据和信息通信技术等多个行业和技术之间的在线连接和交易。 数字经济不同于传统经济,因为它依赖数字技术、在线交易…...
关于APM32F407配置串口DMA收发没有数据的问题记录
一.问题环境 整活了一套APM32F407的板子,用了APM32F4xx_SDK_V1.4的标准外设库,正在搭建移植底层BSP框架串口部分,BSP底层配置逻辑是从STM32F407移植过来的。DMA发送时才使能通道及配置外设地址及缓存大小。 串口1DMA配置过程如下&…...
基于python实现的深度学习web多格式纠错系统
基于python实现的深度学习web多格式纠错系统 开发语言:Python 数据库:MySQL所用到的知识:Django框架工具:pycharm、Navicat、Maven 系统功能实现 用户登录 登录功能是本系统一个非常重要的功能,这极大的保护了系统的安全。登录…...
UE5文件操作
首先在虚幻引擎中创建UMyBlueprintFunctionLibrary类,可以在该类中写我们重复利用的功能,并且这些功能不依赖于特定的游戏对象,方便全局调用。 1.文件的读取和写入 UFUNCTION(BlueprintCallable, Category "File")static bool lo…...
element plus 去掉select选择框的边框,并修改右侧图标
1.去掉选择框边框 ::v-deep .el-select__wrapper{ box-shadow: none; } ::v-deep .is-hovering{ box-shadow: none !important; }2.修改选择框右侧图标 新建CaretBottom.vue文件内容: <template><el-icon><CaretBottom /></el-icon> <…...
Ceph KernelFuse GetSet Quota
Kernel fuse set示例...
JVM学习-字节码指令集(二)
对象的创建与访问指令 创建指令 虽然类实例和数组都是对象,但Java虚拟机对类实例和数组的创建和操作使用了不同的字节码指令创建类实例指令:new 它接收一个操作数,指向常量池的索引,表示要创建的类型,执行完成后&am…...
解密网络流量监控:优化IT运维的利器
引言: 在当今数字化时代,网络流量监控是维护网络稳定与业务连续性的关键。作为一名资深网络工程师,我将分享一些关于网络流量监控的重要知识,并探讨如何在IT运维中运用这一工具优化网络性能,确保业务的顺畅进行。 1. 网…...
oracle 分区表常用语句(2)
给分区表增加分区 第一种不存在MAXVALUE(直接添加即可) ALTER TABLE T6 ADD PARTITION P5 VALUES LESS THAN(TO_DATE( 2018-08-01 00:00:00, SYYYY-MM-DD HH24:MI:SS, NLS_CALENDARGREGORIAN));第二种存在MAXVALUE alter table T6 split PARTITION P4 at(TO_DAT…...
Python函数式编程进阶:用函数实现设计模式
文章目录 函数式编程进阶:用函数实现设计模式案例实现:构建“策略”模式使用函数实现”策略“模式享元 选择最佳策略:简单的方式 globals关键字 函数式编程进阶:用函数实现设计模式 案例实现:构建“策略”模式 策略模…...
Ingress controller:Kubernetes 的瑞士军刀
原文作者:Brian Ehlert of F5 原文链接:Ingress controller:Kubernetes 的瑞士军刀 转载来源:NGINX 中文官网 NGINX 唯一中文官方社区 ,尽在 nginx.org.cn 许多人认为 Ingress controller(Ingress 控制器&…...
通过Wrangler CLI在worker中创建数据库和表
官方使用文档:Getting started Cloudflare D1 docs 创建数据库 在命令行中执行完成之后,会在本地和远程创建数据库: npx wranglerlatest d1 create prod-d1-tutorial 在cf中就可以看到数据库: 现在,您的Cloudfla…...
visual studio 2022更改主题为深色
visual studio 2022更改主题为深色 点击visual studio 上方的 工具-> 选项 在选项窗口中,选择 环境 -> 常规 ,将其中的颜色主题改成深色 点击确定,更改完成...
(二)原型模式
原型的功能是将一个已经存在的对象作为源目标,其余对象都是通过这个源目标创建。发挥复制的作用就是原型模式的核心思想。 一、源型模式的定义 原型模式是指第二次创建对象可以通过复制已经存在的原型对象来实现,忽略对象创建过程中的其它细节。 📌 核心特点: 避免重复初…...
Mac软件卸载指南,简单易懂!
刚和Adobe分手,它却总在Library里给你写"回忆录"?卸载的Final Cut Pro像电子幽灵般阴魂不散?总是会有残留文件,别慌!这份Mac软件卸载指南,将用最硬核的方式教你"数字分手术"࿰…...
pikachu靶场通关笔记22-1 SQL注入05-1-insert注入(报错法)
目录 一、SQL注入 二、insert注入 三、报错型注入 四、updatexml函数 五、源码审计 六、insert渗透实战 1、渗透准备 2、获取数据库名database 3、获取表名table 4、获取列名column 5、获取字段 本系列为通过《pikachu靶场通关笔记》的SQL注入关卡(共10关࿰…...
scikit-learn机器学习
# 同时添加如下代码, 这样每次环境(kernel)启动的时候只要运行下方代码即可: # Also add the following code, # so that every time the environment (kernel) starts, # just run the following code: import sys sys.path.append(/home/aistudio/external-libraries)机…...
前端中slice和splic的区别
1. slice slice 用于从数组中提取一部分元素,返回一个新的数组。 特点: 不修改原数组:slice 不会改变原数组,而是返回一个新的数组。提取数组的部分:slice 会根据指定的开始索引和结束索引提取数组的一部分。不包含…...
学习一下用鸿蒙DevEco Studio HarmonyOS5实现百度地图
在鸿蒙(HarmonyOS5)中集成百度地图,可以通过以下步骤和技术方案实现。结合鸿蒙的分布式能力和百度地图的API,可以构建跨设备的定位、导航和地图展示功能。 1. 鸿蒙环境准备 开发工具:下载安装 De…...
Vue3 PC端 UI组件库我更推荐Naive UI
一、Vue3生态现状与UI库选择的重要性 随着Vue3的稳定发布和Composition API的广泛采用,前端开发者面临着UI组件库的重新选择。一个好的UI库不仅能提升开发效率,还能确保项目的长期可维护性。本文将对比三大主流Vue3 UI库(Naive UI、Element …...
《Offer来了:Java面试核心知识点精讲》大纲
文章目录 一、《Offer来了:Java面试核心知识点精讲》的典型大纲框架Java基础并发编程JVM原理数据库与缓存分布式架构系统设计二、《Offer来了:Java面试核心知识点精讲(原理篇)》技术文章大纲核心主题:Java基础原理与面试高频考点Java虚拟机(JVM)原理Java并发编程原理Jav…...
