当前位置: 首页 > news >正文

滑动窗口练习(二)— 子数组中满足max -min <= sum的个数

题目
给定一个整型数组arr,和一个整数num
某个arr中的子数组sub,如果想达标,必须满足:
sub中最大值 – sub中最小值 <= num,
返回arr中达标子数组的数量

暴力对数器
暴力对数器方法主要是用来和另一个方法互相校验正确性,所以不用考虑时间复杂度。
因为要求的是子数组中的最大值和子数组中的最小值相减 <= num。所以整体思路是这样:
求数组 0 ~ N - 1范围内,所有子数组,找到子数组中最小值,看相减后是否达标,如果达标,则count++进行计数。最后return count。
所有子数组挨个枚举,就是 0~ 0范围内子数组,0 ~ 1范围内子数组 0 ~ N - 1范围内子数组。
1 ~ 1范围内子数组,1 ~ 2 范围内子数组 1 ~ N - 1范围内子数组…。
每个范围内子数组进行枚举,需要两层for循环,找到每个子数组范围内的最大值和最小值,额外需要1层for循环,所以时间复杂度是 O ( N 3 ) O(N^3) ON3

代码

 public static int right(int[] arr, int sum) {if (arr == null || arr.length == 0 || sum < 0) {return 0;}int N = arr.length;int count = 0;for (int L = 0; L < N; L++) {for (int R = L; R < N; R++) {int max = arr[L];int min = arr[L];for (int i = L + 1; i <= R; i++) {min = Math.min(min, arr[i]);max = Math.max(max, arr[i]);}if (max - min <= sum) {count++;}}}return count;}

滑动窗口算法
采用滑动窗口算法的时间复杂度是 O ( N ) O(N) ON,因为窗口不可回退,所以只需要一次遍历即可找出所有符合条件的子数组。
这道题中需要2个窗口,一个维护L…R范围内的最大值,一个维护L…R范围内的最小值。而在看代码之前,需要达成这样的2个共识:

  1. 如果L…R范围内 max - min <= num,那么L…R范围内所有子数组都满足 max - min <= num,都会达标。
  2. 如果L…R范围内 max - min > num,那么无论R继续向右扩窗口或者L继续向左阔窗口,那L…R范围内子数组依然不达标。

解释1:
因为max - min <= num,所以L…R 范围内剩余子数组相减,子数组范围内的两个数一定是 < max && > min的,最大值变小了,最小值变大了,所以一定会<= num。
解释2:
因为max - min > num,根据滑动窗口的特性,在维护L…R范围内最大值的双端队列中,后进来的数一定是>=当前双端队列中的值才会进行替换,在维护L…R范围内最小值的双端队列中,后进来的数一定是<=当前双端队列中的值才会进行替换。 所以无论向右或者向左,范围内子数组一定依然不达标。

达成这两个共识之后,代码就简单了很多,在维护双端队列特性的同时,如果满足 max - min <= num,则R向右移,直到不满足 max - min <= num为止。碰见一次不满足,则计算一次当前子数组的个数,直到循环完成。

代码

public static int num(int[] arr, int sum) {if (arr == null || arr.length == 0  || sum < 0) {return 0;}LinkedList<Integer> minWindow = new LinkedList<>();LinkedList<Integer> maxWindow = new LinkedList<>();int R = 0;int count = 0;int N = arr.length;for (int L = 0; L < N; L++) {while (R < N) {//如果max双端队列不为null,并且队列尾端值<=当前值,则弹出while (!maxWindow.isEmpty() && arr[maxWindow.peekLast()] <= arr[R]) {maxWindow.pollLast();}maxWindow.addLast(R);//如果min双端队列不为null,并且队列尾端值>=当前值,则弹出while (!minWindow.isEmpty() && arr[minWindow.peekLast()] >= arr[R]) {minWindow.pollLast();}minWindow.addLast(R);//如果满足条件,则R一直++, 直到不满足条件为止if (arr[maxWindow.peekFirst()] - arr[minWindow.peekFirst()] <= sum) {R++;} else {break;}}//看R - L范围内共有多少个子数组count += R - L;//因为这两个判断走完L就要进行++//所以需要判断当前双端队列中头部值是否要过期了if (maxWindow.peekFirst() == L) {maxWindow.pollFirst();}if (minWindow.peekFirst() == L) {minWindow.pollFirst();}}return count;}

测试
随机生成数组和sum,采用大数据样本量进行测试,用上面两个方法来相互验证。

public static int[] generateRandomArray(int maxLength, int maxValue) {int[] arr = new int[(int) ((maxLength + 1) * Math.random())];for (int i = 0; i < arr.length; i++) {arr[i] = (int) ((maxValue + 1) * Math.random());}return arr;}public static void main(String[] args) {int maxLength = 40;int maxValue = 10000;int sum = 10000;int testNum = 1000000;System.out.println("测试开始");for (int i = 0; i < testNum; i++) {int[] arr = generateRandomArray(maxLength, maxValue);sum = (int) ((sum + 1) * Math.random());int ans1 = right(arr, sum);int ans2 = num(arr, sum);if (ans1 != ans2) {for (int num : arr) {System.out.print(num + " ");}System.out.println();System.out.println("sum : " + sum);System.out.println("ans1 : " + ans1);System.out.println("ans2 : " + ans2);System.out.println("Oops!!");break;}}System.out.println("测试结束");}

相关文章:

滑动窗口练习(二)— 子数组中满足max -min <= sum的个数

题目 给定一个整型数组arr&#xff0c;和一个整数num 某个arr中的子数组sub&#xff0c;如果想达标&#xff0c;必须满足&#xff1a; sub中最大值 – sub中最小值 < num&#xff0c; 返回arr中达标子数组的数量 暴力对数器 暴力对数器方法主要是用来和另一个方法互相校验正…...

用xlwings新建一个excel并同时生成多个sheet

新建一个excel并同时生成多个sheet&#xff0c;要实现如下效果&#xff1a; 一般要使用数据透视表来快速实现。 今天记录用xlwings新建一个excel并同时生成多个sheet。 import xlwings as xw # 打开excel,参数visible表示处理过程是否可视,add_book表示是否打开新的Excel程序…...

诺威信,浪潮云,微众区块链

目录 诺威信B隐私计算平台 浪潮云=星火连-澳优码 HyperChain 产品介绍 CA认证即电子认证服务...

Redux在React中的使用

Redux在React中的使用 1.构建方式 采用reduxjs/toolkitreact-redux的方式 安装方式 npm install reduxjs/toolkit react-redux2.使用 ①创建目录 创建store文件夹&#xff0c;然后创建index和对应的模块&#xff0c;如上图所示 ②编写counterStore.js 文章以counterStore…...

Go 数字类型

一、数字类型 1、Golang 数据类型介绍 Go 语言中数据类型分为&#xff1a;基本数据类型和复合数据类型基本数据类型有&#xff1a; 整型、浮点型、布尔型、字符串复合数据类型有&#xff1a; 数组、切片、结构体、函数、map、通道&#xff08;channel&#xff09;、接口 2、…...

时间序列预测 — Informer实现多变量负荷预测(PyTorch)

目录 1 实验数据集 2 如何运行自己的数据集 3 报错分析 1 实验数据集 实验数据集采用数据集4&#xff1a;2016年电工数学建模竞赛负荷预测数据集&#xff08;下载链接&#xff09;&#xff0c;数据集包含日期、最高温度℃ 、最低温度℃、平均温度℃ 、相对湿度(平均) 、降雨…...

2023年金融信创行业研究报告

第一章 行业概况 1.1 定义 金融信创是指在金融行业中应用的信息技术&#xff0c;特别是那些涉及到金融IT基础设施、基础软件、应用软件和信息安全等方面的技术和产品。这一概念源于更广泛的“信创 (信息技术应用创新)”&#xff0c;即通过中国国产信息技术替换海外信息技术&a…...

51单片机按键控制LED灯亮灭的N个玩法

51单片机按键控制LED灯亮灭的N个玩法 1.概述 这篇文章介绍按键的使用&#xff0c;以及通过控制LED灯的小实验&#xff0c;发现按键中存在的问题&#xff0c;然后思考并解决这些问题。达到熟练使用按键控制元器件。 2.搭建硬件环境 1.硬件准备 名称型号数量单片机STC12C205…...

推荐6款本周 yyds 的开源项目

&#x1f525;&#x1f525;&#x1f525;本周GitHub项目圈选: 主要包含 链接管理、视频总结、有道音色情感合成、中文文本格式校正、GPT爬虫、深度学习推理 等热点项目。 1、Dub 一个开源的链接管理工具&#xff0c;可自定义域名将繁杂的长链接生成短链接&#xff0c;便于保…...

【Git】git 更换远程仓库地址三种方法总结分享

因为公司更改了 gitlab 的网段地址&#xff0c;发现全部项目都需要重新更改远程仓库的地址了&#xff0c;所以做了个记录&#xff0c;说不定以后还会用到呢。 一、不删除远程仓库修改&#xff08;最方便&#xff09; # 查看远端地址 git remote -v # 查看远端仓库名 git rem…...

springboot 返回problem+json

spring所有配置都在WebMvcAutoConfiguration中 其中有 ProblemDetailsExceptionHandler 容器中的一个组件 -ControllerAdvice用来集中处理异常的 -点进ResponseEntityExceptionHandler 包含这些异常&#xff0c;如果出现以下异常&#xff0c;会被springboot支持以RFC 7807规…...

AI动画制作 StableDiffusion

1.brew -v 2.安装爬虫项目包所必需的python和git等系列系统支持部件 brew install cmake protobuf rust python@3.10 git wget pod --version brew link --overwrite cocoapods 3.从github网站克隆stable-diffusion-webui爬虫项目包至本地 ssh-add /Users/haijunyan/.ssh/id_r…...

【开源】基于Vue和SpringBoot的木马文件检测系统

项目编号&#xff1a; S 041 &#xff0c;文末获取源码。 \color{red}{项目编号&#xff1a;S041&#xff0c;文末获取源码。} 项目编号&#xff1a;S041&#xff0c;文末获取源码。 目录 一、摘要1.1 项目介绍1.2 项目录屏 二、功能模块2.1 数据中心模块2.2 木马分类模块2.3 木…...

5 动态规划解分割等和子串

来源&#xff1a;LeetCode第416题 难度&#xff1a;中等 描述&#xff1a;给你一个只包含正整数的非空数组nums,请你判断是否可以将这个数组分割成两个子集&#xff0c;使得两个子集的元素和相等 分析&#xff1a;相当于从nums数组中选取一些元素&#xff0c;使得他们的和为…...

file_get_contents() 函数详解与使用

概述 在PHP中&#xff0c;file_get_contents() 函数是一个强大的工具&#xff0c;它既可以用于读取本地文件的内容&#xff0c;也可以用于发起 HTTP 请求获取远程资源。本文将详细介绍 file_get_contents() 函数的两种主要用途&#xff0c;并探讨如何充分利用这个函数。 1. 文…...

某医生用 ChatGPT 在 4 个月内狂写 16 篇论文,其中 5 篇已发表,揭密ChatGPT进行论文润色与改写的秘籍

如果写过学术论文&#xff0c;想必会有这样的感受&#xff1a; 绞尽脑汁、茶饭不思、夜不能寐、废寝忘食、夜以继日&#xff0c;赶出一篇论文&#xff0c;然后还被导师点评&#xff0c;“写得就是一坨&#xff01;” 可是&#xff0c;却有人4个月产出了16篇论文&#xff0c;成功…...

进程等待讲解

今日为大家分享有关进程等待的知识&#xff01;希望读完本文&#xff0c;大家能有一定的收获&#xff01; 正文开始&#xff01; 进程等待的引进 既然我们今天要讲进程等待这个概念&#xff01;那么只有我们把下面这三个方面搞明白&#xff0c;才能真正的了解进程等待&#x…...

MySQL Binlog深度解析:进阶应用与实战技巧【进阶应用】

&#x1f38f;&#xff1a;你只管努力&#xff0c;剩下的交给时间 &#x1f3e0; &#xff1a;小破站 MySQL Binlog深度解析&#xff1a;进阶应用与实战技巧 前言第一&#xff1a;Binlog事件详解第二&#xff1a;关于GTIDGTID的结构&#xff1a;GTID的作用&#xff1a;GTID的事…...

openpnp - 给底部相机加防尘罩

文章目录 openpnp - 给底部相机加防尘罩概述笔记END openpnp - 给底部相机加防尘罩 概述 设备标定完, 看着底部相机, 有点担心掉进去东西, 万一从吸嘴掉下去的料(或者清理设备台面时, 不小心掉进去东西)将顶部相机搞短路怎么办. 就想加个防尘罩, 如果有东西掉进去, 可以掉到机…...

mac mysql连接中断重新启动办法

遇到如图所示问题&#xff0c;可以用下面的命令重启mysql服务 sudo /usr/local/mysql/support-files/mysql.server start...

TlbbGmTool:重构游戏管理体验的5大架构创新解析

TlbbGmTool&#xff1a;重构游戏管理体验的5大架构创新解析 【免费下载链接】TlbbGmTool 某网络游戏的单机版本GM工具 项目地址: https://gitcode.com/gh_mirrors/tl/TlbbGmTool 从命令行困境到可视化治理的游戏运维实践指南 一、价值定位&#xff1a;重新定义游戏管理…...

被裁两次,赔了30万,我真得感谢公司。21年赔10万,24年赔20万,平时月光,全靠裁员攒下第一桶金

今天刷到一个帖子&#xff0c;一个程序员说自己被裁了两次&#xff0c;21年赔了10万&#xff0c;24年赔了20万&#xff0c;加起来30万。他说平时一分钱都攒不下&#xff0c;全靠这两次裁员才有了存款&#xff0c;真得感谢公司。我第一反应是&#xff1a;这话听着挺魔幻&#xf…...

OpenClaw未来展望:Qwen3-4B模型与自动化生态的演进方向

OpenClaw未来展望&#xff1a;Qwen3-4B模型与自动化生态的演进方向 1. 从个人实践看OpenClaw的现状与挑战 去年冬天&#xff0c;当我第一次在本地MacBook上部署OpenClaw时&#xff0c;那种"让AI直接操控我的电脑"的新奇感至今难忘。通过简单的自然语言指令&#xf…...

提升电路设计效率:快马AI一键生成三极管偏置方案与对比报告

作为一名电子工程师&#xff0c;经常需要设计三极管放大电路&#xff0c;其中最基础也最繁琐的就是偏置电路的计算。传统方法需要手动查公式、反复验算&#xff0c;不仅耗时还容易出错。最近发现InsCode(快马)平台可以快速生成三极管偏置方案&#xff0c;体验后发现确实能大幅提…...

OpenClaw技能组合技:Qwen3-14b_int4_awq串联多个自动化流程

OpenClaw技能组合技&#xff1a;Qwen3-14b_int4_awq串联多个自动化流程 1. 为什么需要技能组合技&#xff1f; 去年我接手了一个数据收集项目&#xff0c;需要每天从10个不同网站爬取数据&#xff0c;清洗后生成报告并通过邮件发送给团队成员。最初我尝试手动操作&#xff0c…...

华新嘉华:如何做好GEO?记住!简单的内容堆砌达不到效果

‍在生成式AI搜索全面重塑信息获取方式的当下&#xff0c;越来越多的企业开始布局GEO&#xff08;生成式引擎优化&#xff09;&#xff0c;希望抢占AI搜索这一新兴流量入口。然而&#xff0c;一个不容忽视的现象正在蔓延&#xff1a;大量企业投入资源、批量生产内容&#xff0c…...

【人工智能基础-机器学习】- 线性归回知识点(有个人理解)

机器学习&#xff1a;线性回归 一、线性回归基础 1.1 数据准备 将x0置为1&#xff0c;与xn组合得到nn的矩阵 1.2 理论基础 正态分布&#xff1a; 基于中心极限定理&#xff0c;误差&#xff08;预测值-实际值&#xff09;服从正态分布 最大似然估计&#xff08;MLE&#xff09;…...

视觉障碍辅助:OpenClaw+Phi-3-vision-128k-instruct实时描述周围环境

视觉障碍辅助&#xff1a;OpenClawPhi-3-vision-128k-instruct实时描述周围环境 1. 项目背景与核心需求 去年在帮助一位视障朋友调试智能家居时&#xff0c;我意识到现有环境感知工具存在明显断层——要么是功能单一的"拍照识物"APP&#xff0c;要么是昂贵的企业级…...

seo北京优化和网站内容优化有什么联系

SEO北京优化与网站内容优化的紧密联系 在当今互联网时代&#xff0c;对于任何企业来说&#xff0c;网站的优化是至关重要的一环。尤其是在竞争激烈的北京市场&#xff0c;SEO&#xff08;搜索引擎优化&#xff09;和网站内容优化之间的关系更加紧密。本文将从问题分析、原因说…...

Qt【第七篇】 ——— QSS 样式表与绘图 API 核心用法及 UI 定制功能总结

目录 QSS widget.cpp&#xff08;QSS的基本使用&#xff09; widget.cpp&#xff08;QSS选择器的用法&#xff09; widget.cpp&#xff08;QSS子控件选择器&#xff09; widget.cpp&#xff08;QSS伪类选择器&#xff09; widget.cpp&#xff08;QSS盒子模型&#xff09; QSS 基…...