滑动窗口系列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 的元素࿰…...
数据链路层的主要功能是什么
数据链路层(OSI模型第2层)的核心功能是在相邻网络节点(如交换机、主机)间提供可靠的数据帧传输服务,主要职责包括: 🔑 核心功能详解: 帧封装与解封装 封装: 将网络层下发…...
从零开始打造 OpenSTLinux 6.6 Yocto 系统(基于STM32CubeMX)(九)
设备树移植 和uboot设备树修改的内容同步到kernel将设备树stm32mp157d-stm32mp157daa1-mx.dts复制到内核源码目录下 源码修改及编译 修改arch/arm/boot/dts/st/Makefile,新增设备树编译 stm32mp157f-ev1-m4-examples.dtb \stm32mp157d-stm32mp157daa1-mx.dtb修改…...
Android Bitmap治理全解析:从加载优化到泄漏防控的全生命周期管理
引言 Bitmap(位图)是Android应用内存占用的“头号杀手”。一张1080P(1920x1080)的图片以ARGB_8888格式加载时,内存占用高达8MB(192010804字节)。据统计,超过60%的应用OOM崩溃与Bitm…...
iOS性能调优实战:借助克魔(KeyMob)与常用工具深度洞察App瓶颈
在日常iOS开发过程中,性能问题往往是最令人头疼的一类Bug。尤其是在App上线前的压测阶段或是处理用户反馈的高发期,开发者往往需要面对卡顿、崩溃、能耗异常、日志混乱等一系列问题。这些问题表面上看似偶发,但背后往往隐藏着系统资源调度不当…...
推荐 github 项目:GeminiImageApp(图片生成方向,可以做一定的素材)
推荐 github 项目:GeminiImageApp(图片生成方向,可以做一定的素材) 这个项目能干嘛? 使用 gemini 2.0 的 api 和 google 其他的 api 来做衍生处理 简化和优化了文生图和图生图的行为(我的最主要) 并且有一些目标检测和切割(我用不到) 视频和 imagefx 因为没 a…...
Neko虚拟浏览器远程协作方案:Docker+内网穿透技术部署实践
前言:本文将向开发者介绍一款创新性协作工具——Neko虚拟浏览器。在数字化协作场景中,跨地域的团队常需面对实时共享屏幕、协同编辑文档等需求。通过本指南,你将掌握在Ubuntu系统中使用容器化技术部署该工具的具体方案,并结合内网…...
Java详解LeetCode 热题 100(26):LeetCode 142. 环形链表 II(Linked List Cycle II)详解
文章目录 1. 题目描述1.1 链表节点定义 2. 理解题目2.1 问题可视化2.2 核心挑战 3. 解法一:HashSet 标记访问法3.1 算法思路3.2 Java代码实现3.3 详细执行过程演示3.4 执行结果示例3.5 复杂度分析3.6 优缺点分析 4. 解法二:Floyd 快慢指针法(…...
JS红宝书笔记 - 3.3 变量
要定义变量,可以使用var操作符,后跟变量名 ES实现变量初始化,因此可以同时定义变量并设置它的值 使用var操作符定义的变量会成为包含它的函数的局部变量。 在函数内定义变量时省略var操作符,可以创建一个全局变量 如果需要定义…...
CppCon 2015 学习:REFLECTION TECHNIQUES IN C++
关于 Reflection(反射) 这个概念,总结一下: Reflection(反射)是什么? 反射是对类型的自我检查能力(Introspection) 可以查看类的成员变量、成员函数等信息。反射允许枚…...
【Qt】控件 QWidget
控件 QWidget 一. 控件概述二. QWidget 的核心属性可用状态:enabled几何:geometrywindows frame 窗口框架的影响 窗口标题:windowTitle窗口图标:windowIconqrc 机制 窗口不透明度:windowOpacity光标:cursor…...
