滑动窗口系列1-达标子数组
#达标子数组#
求达标子数组的数量 * 题目:给定一个数组,求满足子数组中最大值-最小值小于等于某个数的子数组的数量 * 例如[0,1,2,3]中求子数组中最大值-最小值小于等于 2的子数组的数量 * 结果为9,因为满足条件的只有[0,0] [0,1] [0,2] [1,1] [1,2] [1,3] [2,2] [2,3] [3,3]
题目对应的代码如下:
首先讨论暴力解,这种解法特别容易想,就是把所有的子数组进行枚举,例如:0~0,0~1,0~2,0~3, 0~4...2~2,2~2,2~3,2~4...然后依次找到每个子数组的最大值和最小值,根据二者之差判断是否达标,如果达标则总的数量加1,两层for循环的时间复杂度是O(N^2),面试场没分
重点讨论第二种解法,也是本题的重要考察点:滑动窗口,对于滑动窗口解法来说,每个位置最多进一次窗口,也最多出一次窗口,所以时间复杂度是O(N),这个已经是最好的解法了,你不可能所有的位置都没看完就找到所有答案
public class AllLessNumSubArray {/*** 暴力解,百分百正确,但是面试场上没分*/public static int right(int[] nums, int limit) {if(nums == null || nums.length == 0 || limit < 0) {return 0;}int result = 0;for(int i = 0; i < nums.length; i++) {int max = nums[i];int min = nums[i];for(int j = i; j < nums.length; j++) {max = Math.max(max, nums[j]);min = Math.min(min, nums[j]);if(max - min > limit) break;if(max - min <= limit) result ++;}}return result;}public static int better(int[] nums, int limit) {//不满足基本的条件,返回0个if(nums == null || nums.length == 0 || limit < 0) {return 0;}//数组的长度int N = nums.length;//创建最大值和最小值窗口,使用双端队列LinkedList<Integer> min = new LinkedList<>();LinkedList<Integer> max = new LinkedList<>();//L和R都从0开始,形成的区间是[L,R]左开右闭int R = 0;int L = 0;//最终结果统计int result = 0;//L,R的边界都是小于N,都是不回退的while(L < N) {while(R < N) {//如果当前最小值窗口中有数字大于要进去的R的位置的数字,依次弹出while(!min.isEmpty() && nums[min.peekLast()] >= nums[R]) {min.pollLast();}//R入最小值窗口min.addLast(R);//如果当前最大值窗口中有数字小于要进去的R的位置的数字,依次弹出while(!max.isEmpty() && nums[max.peekLast()] <= nums[R]) {max.pollLast();}//R入最小值窗口max.addLast(R);//当前窗口最大值-最小值如果不满足《=limit,终止,//如果满足条件R继续++,R是以L下标开始第一个不满足条件的if(nums[max.peekFirst()] - nums[min.peekFirst()] > limit) {break;} else {R++;}}//因为L马上要进行L++操作了,所以L位置马上过期,如果最大值或者最小值窗口的头部是L,则弹出头部if(max.peekFirst() == L) {max.pollFirst();}if(min.peekFirst() == L) {min.pollFirst();}//R是以L为起点的子数组中第一个不满足max-min<=limit的节点,所以数量加上(R - L)result += (R - L);L++;}return result;}}
相关文章:
滑动窗口系列1-达标子数组
#达标子数组# 求达标子数组的数量 * 题目:给定一个数组,求满足子数组中最大值-最小值小于等于某个数的子数组的数量 * 例如[0,1,2,3]中求子数组中最大值-最小值小于等于 2的子数组的数量 * 结果为9,因为满足条件的只有[0,0] [0,1] [0,2] [1,1] [1,2] [1…...
电视显示技术及价格成本对比(2023年)
版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 本文链接:https://blog.csdn.net/zaibeijixing/article/details/132461068 ———————————————— 截止到2023年ÿ…...
浅谈 Pytest+HttpRunner 如何展开接口测试!
软件测试有多种多样的方法和技术,可以从不同角度对它们进行分类。其中,根据软件生命周期,针对不同的测试对象与目标,可将测试过程分为 4 个阶段:单元测试、集成测试、系统测试和验收测试。本文着重介绍了如何借用 pyte…...
vue自定义事件 div 拖拽方法缩小
在main.js 引用 // 引入拖动js import dragMove from "./utils/dragMove.js" 创建 drawmove.js export default (app) > {app.directive(dragMove, (el, binding) > {const DragVindow el.querySelector(binding.value.DragVindow)// 按下鼠标处理事件con…...
使用实体解析和图形神经网络进行欺诈检测
图形神经网络的表示形式(作者使用必应图像创建器生成的图像) 一、说明 对于金融、电子商务和其他相关行业来说,在线欺诈是一个日益严重的问题。为了应对这种威胁,组织使用基于机器学习和行为分析的欺诈检测机制。这些技术能够实时…...
vue中axios请求篇
vue中如何发起请求? 利用axios来发起请求,但是前期需要配置 首先安装axios 可以使用npm、yarn等进行安装 npm安装方式 npm install axios -sava //在项目文件夹中打开cmd或者终端进行安装依赖 yarn安装方式 yarn add axios 引入axios。我一般是在src下创建一个u…...
Springboot2.0 上传图片 jar包导出启动(第二章)
目录 一,目录文件结构讲解二,文件上传实战三,jar包方式运行web项目的文件上传和访问处理(核心知识)最后 一,目录文件结构讲解 简介:讲解SpringBoot目录文件结构和官方推荐的目录规范 1、目录讲解…...
添加YDNS免费的ipv6动态域名解析
背景 又到了一年一度的dns域名到期,寻找替代了,前几年用了阿里、华为的免费域名,支持了几个搭建在NAS上的微服务;一旦涉及到域名续费,价格就比首年上去了不少,所以,打算找个长期的免费域名。 搜…...
爬虫异常处理之如何处理连接丢失和数据存储异常
在爬虫开发过程中,我们可能会遇到各种异常情况,如连接丢失、数据存储异常等。本文将介绍如何处理这些异常,并提供具体的解决代码。我们将以Python语言为例,使用requests库进行网络请求和sqlite3库进行数据存储。 1. 处理连接丢失 …...
KVM虚拟化ubuntu
KVM(Kernel-based Virtual Machine)是一种基于Linux内核的虚拟化技术,它将Linux内核作为虚拟机的底层操作系统,利用硬件虚拟化支持创建和管理虚拟机。KVM虚拟化技术被广泛应用于云计算、虚拟化服务器、虚拟化桌面等场景。 KVM虚拟…...
模拟电子技术基础学习笔记三 PN结
采用不周的掺杂工艺,将P型半导体与N型半导体制作在同一块硅片上,在它们的交界面就形成PN结。 扩散运动 物质总是从浓度高的地方向浓度低的地方运动,这种由于浓度差而产生的运动称为扩散运动。 空间电荷区 - 耗尽层 漂移运动 在电场力的作…...
java基础-----第七篇
系列文章目录 文章目录 系列文章目录一、什么是字节码?采用字节码的好处是什么?1.java中的编译器和解释器:2.采用字节码的好处:二、Java中的异常体系一、什么是字节码?采用字节码的好处是什么? 1.java中的编译器和解释器: Java中引入了虚拟机的概念,即在机器和编译程…...
useEffect 不可忽视的 cleanup 函数
在 react 开发中, useEffect 是我们经常会使用到的钩子,一个基础的例子如下: useEffect(() > {// some code here// cleanup 函数return () > {doSomething()} }, [dependencies])上述代码中, cleanup 函数的执行时机有如下…...
vue3:使用:批量删除功能
场景:vue中使用el-table,常需要记住上一页所勾选的数据,批量删除操作,或者弹窗分页勾选,进行第一页勾选,在调后端接口选择第二页勾选其他数据。 1、element-ui 的table表格可以轻松实现多选的功能,只要在表…...
Scala中的样例类和样例对象和JAVA存根类
Scala中的样例类和样例对象 在 Scala 中,样例类(case class)和样例对象(case object)都是用于定义不可变数据类型的特殊类和对象。它们被广泛用于模式匹配、代数数据类型(Algebraic Data Types)…...
【0218】当SIGQUIT kill掉stats collector后,stats collector如何保存最终统计数据
1. stats collector可被哪些信号给kill? stats collector进程的主体函数是 PgstatCollectorMain(),该函数内部完成了stats collector进程的信号注册、现有统计文件读取、消息处理等任务。 忽略通常与postmaster中的某些操作绑定的所有信号,SIGHUP和SIGQUIT除外。 注意,我们…...
httplib 与 json.hpp 结合示例
httplib 与 json.hpp 结合示例 1、使用POST 接口,发送 登陆 请求 客户端发送 {nlohmann::json jsonOfCollectionInfo;jsonOfCollectionInfo["user_id"] "zhang";jsonOfCollectionInfo["password"] "123456";httplib::…...
RK3288安卓7.1开机上电到显示logo需要在3s内完成
需求: 从上电到开始开机logo有一段黑屏时间,这个黑屏时间大概在6s左右,给客户体验很不好,现在需要将这段黑屏时间缩短到2-3s左右 思路: 因为只需要早点显示logo,其实整体从上电到开机动画到安卓系统启动整体…...
Maven之hibernate-validator 高版本问题
hibernate-validator 高版本问题 hibernate-validator 的高版本(邮箱注解)依赖于高版本的 el-api,tomcat 8 的 el-api 是 3.0,满足需要。但是 tomcat 7 的 el-api 只有 2.2,不满足其要求。 解决办法有 2 种ÿ…...
C++--动态规划其他问题
1.一和零 力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台 给你一个二进制字符串数组 strs 和两个整数 m 和 n 。 请你找出并返回 strs 的最大子集的长度,该子集中 最多 有 m 个 0 和 n 个 1 。 如果 x 的所有元素也是 y 的元素࿰…...
Redis相关知识总结(缓存雪崩,缓存穿透,缓存击穿,Redis实现分布式锁,如何保持数据库和缓存一致)
文章目录 1.什么是Redis?2.为什么要使用redis作为mysql的缓存?3.什么是缓存雪崩、缓存穿透、缓存击穿?3.1缓存雪崩3.1.1 大量缓存同时过期3.1.2 Redis宕机 3.2 缓存击穿3.3 缓存穿透3.4 总结 4. 数据库和缓存如何保持一致性5. Redis实现分布式…...
循环冗余码校验CRC码 算法步骤+详细实例计算
通信过程:(白话解释) 我们将原始待发送的消息称为 M M M,依据发送接收消息双方约定的生成多项式 G ( x ) G(x) G(x)(意思就是 G ( x ) G(x) G(x) 是已知的)࿰…...
Auto-Coder使用GPT-4o完成:在用TabPFN这个模型构建一个预测未来3天涨跌的分类任务
通过akshare库,获取股票数据,并生成TabPFN这个模型 可以识别、处理的格式,写一个完整的预处理示例,并构建一个预测未来 3 天股价涨跌的分类任务 用TabPFN这个模型构建一个预测未来 3 天股价涨跌的分类任务,进行预测并输…...
RNN避坑指南:从数学推导到LSTM/GRU工业级部署实战流程
本文较长,建议点赞收藏,以免遗失。更多AI大模型应用开发学习视频及资料,尽在聚客AI学院。 本文全面剖析RNN核心原理,深入讲解梯度消失/爆炸问题,并通过LSTM/GRU结构实现解决方案,提供时间序列预测和文本生成…...
MySQL账号权限管理指南:安全创建账户与精细授权技巧
在MySQL数据库管理中,合理创建用户账号并分配精确权限是保障数据安全的核心环节。直接使用root账号进行所有操作不仅危险且难以审计操作行为。今天我们来全面解析MySQL账号创建与权限分配的专业方法。 一、为何需要创建独立账号? 最小权限原则…...
基于 TAPD 进行项目管理
起因 自己写了个小工具,仓库用的Github。之前在用markdown进行需求管理,现在随着功能的增加,感觉有点难以管理了,所以用TAPD这个工具进行需求、Bug管理。 操作流程 注册 TAPD,需要提供一个企业名新建一个项目&#…...
C++课设:简易日历程序(支持传统节假日 + 二十四节气 + 个人纪念日管理)
名人说:路漫漫其修远兮,吾将上下而求索。—— 屈原《离骚》 创作者:Code_流苏(CSDN)(一个喜欢古诗词和编程的Coder😊) 专栏介绍:《编程项目实战》 目录 一、为什么要开发一个日历程序?1. 深入理解时间算法2. 练习面向对象设计3. 学习数据结构应用二、核心算法深度解析…...
免费数学几何作图web平台
光锐软件免费数学工具,maths,数学制图,数学作图,几何作图,几何,AR开发,AR教育,增强现实,软件公司,XR,MR,VR,虚拟仿真,虚拟现实,混合现实,教育科技产品,职业模拟培训,高保真VR场景,结构互动课件,元宇宙http://xaglare.c…...
springboot 日志类切面,接口成功记录日志,失败不记录
springboot 日志类切面,接口成功记录日志,失败不记录 自定义一个注解方法 import java.lang.annotation.ElementType; import java.lang.annotation.Retention; import java.lang.annotation.RetentionPolicy; import java.lang.annotation.Target;/***…...
k8s从入门到放弃之HPA控制器
k8s从入门到放弃之HPA控制器 Kubernetes中的Horizontal Pod Autoscaler (HPA)控制器是一种用于自动扩展部署、副本集或复制控制器中Pod数量的机制。它可以根据观察到的CPU利用率(或其他自定义指标)来调整这些对象的规模,从而帮助应用程序在负…...
