小白如何如何理解滑动窗口最大值问题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 控制器&…...
UE5 学习系列(二)用户操作界面及介绍
这篇博客是 UE5 学习系列博客的第二篇,在第一篇的基础上展开这篇内容。博客参考的 B 站视频资料和第一篇的链接如下: 【Note】:如果你已经完成安装等操作,可以只执行第一篇博客中 2. 新建一个空白游戏项目 章节操作,重…...
R语言AI模型部署方案:精准离线运行详解
R语言AI模型部署方案:精准离线运行详解 一、项目概述 本文将构建一个完整的R语言AI部署解决方案,实现鸢尾花分类模型的训练、保存、离线部署和预测功能。核心特点: 100%离线运行能力自包含环境依赖生产级错误处理跨平台兼容性模型版本管理# 文件结构说明 Iris_AI_Deployme…...
Cinnamon修改面板小工具图标
Cinnamon开始菜单-CSDN博客 设置模块都是做好的,比GNOME简单得多! 在 applet.js 里增加 const Settings imports.ui.settings;this.settings new Settings.AppletSettings(this, HTYMenusonichy, instance_id); this.settings.bind(menu-icon, menu…...
高效线程安全的单例模式:Python 中的懒加载与自定义初始化参数
高效线程安全的单例模式:Python 中的懒加载与自定义初始化参数 在软件开发中,单例模式(Singleton Pattern)是一种常见的设计模式,确保一个类仅有一个实例,并提供一个全局访问点。在多线程环境下,实现单例模式时需要注意线程安全问题,以防止多个线程同时创建实例,导致…...
音视频——I2S 协议详解
I2S 协议详解 I2S (Inter-IC Sound) 协议是一种串行总线协议,专门用于在数字音频设备之间传输数字音频数据。它由飞利浦(Philips)公司开发,以其简单、高效和广泛的兼容性而闻名。 1. 信号线 I2S 协议通常使用三根或四根信号线&a…...
Windows安装Miniconda
一、下载 https://www.anaconda.com/download/success 二、安装 三、配置镜像源 Anaconda/Miniconda pip 配置清华镜像源_anaconda配置清华源-CSDN博客 四、常用操作命令 Anaconda/Miniconda 基本操作命令_miniconda创建环境命令-CSDN博客...
WebRTC从入门到实践 - 零基础教程
WebRTC从入门到实践 - 零基础教程 目录 WebRTC简介 基础概念 工作原理 开发环境搭建 基础实践 三个实战案例 常见问题解答 1. WebRTC简介 1.1 什么是WebRTC? WebRTC(Web Real-Time Communication)是一个支持网页浏览器进行实时语音…...
手机平板能效生态设计指令EU 2023/1670标准解读
手机平板能效生态设计指令EU 2023/1670标准解读 以下是针对欧盟《手机和平板电脑生态设计法规》(EU) 2023/1670 的核心解读,综合法规核心要求、最新修正及企业合规要点: 一、法规背景与目标 生效与强制时间 发布于2023年8月31日(OJ公报&…...
通过 Ansible 在 Windows 2022 上安装 IIS Web 服务器
拓扑结构 这是一个用于通过 Ansible 部署 IIS Web 服务器的实验室拓扑。 前提条件: 在被管理的节点上安装WinRm 准备一张自签名的证书 开放防火墙入站tcp 5985 5986端口 准备自签名证书 PS C:\Users\azureuser> $cert New-SelfSignedCertificate -DnsName &…...
【java】【服务器】线程上下文丢失 是指什么
目录 ■前言 ■正文开始 线程上下文的核心组成部分 为什么会出现上下文丢失? 直观示例说明 为什么上下文如此重要? 解决上下文丢失的关键 总结 ■如果我想在servlet中使用线程,代码应该如何实现 推荐方案:使用 ManagedE…...
