当前位置: 首页 > 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...

KubeSphere 容器平台高可用:环境搭建与可视化操作指南

Linux_k8s篇 欢迎来到Linux的世界&#xff0c;看笔记好好学多敲多打&#xff0c;每个人都是大神&#xff01; 题目&#xff1a;KubeSphere 容器平台高可用&#xff1a;环境搭建与可视化操作指南 版本号: 1.0,0 作者: 老王要学习 日期: 2025.06.05 适用环境: Ubuntu22 文档说…...

TDengine 快速体验(Docker 镜像方式)

简介 TDengine 可以通过安装包、Docker 镜像 及云服务快速体验 TDengine 的功能&#xff0c;本节首先介绍如何通过 Docker 快速体验 TDengine&#xff0c;然后介绍如何在 Docker 环境下体验 TDengine 的写入和查询功能。如果你不熟悉 Docker&#xff0c;请使用 安装包的方式快…...

ubuntu搭建nfs服务centos挂载访问

在Ubuntu上设置NFS服务器 在Ubuntu上&#xff0c;你可以使用apt包管理器来安装NFS服务器。打开终端并运行&#xff1a; sudo apt update sudo apt install nfs-kernel-server创建共享目录 创建一个目录用于共享&#xff0c;例如/shared&#xff1a; sudo mkdir /shared sud…...

JDK 17 新特性

#JDK 17 新特性 /**************** 文本块 *****************/ python/scala中早就支持&#xff0c;不稀奇 String json “”" { “name”: “Java”, “version”: 17 } “”"; /**************** Switch 语句 -> 表达式 *****************/ 挺好的&#xff…...

均衡后的SNRSINR

本文主要摘自参考文献中的前两篇&#xff0c;相关文献中经常会出现MIMO检测后的SINR不过一直没有找到相关数学推到过程&#xff0c;其中文献[1]中给出了相关原理在此仅做记录。 1. 系统模型 复信道模型 n t n_t nt​ 根发送天线&#xff0c; n r n_r nr​ 根接收天线的 MIMO 系…...

让回归模型不再被异常值“带跑偏“,MSE和Cauchy损失函数在噪声数据环境下的实战对比

在机器学习的回归分析中&#xff0c;损失函数的选择对模型性能具有决定性影响。均方误差&#xff08;MSE&#xff09;作为经典的损失函数&#xff0c;在处理干净数据时表现优异&#xff0c;但在面对包含异常值的噪声数据时&#xff0c;其对大误差的二次惩罚机制往往导致模型参数…...

【Redis】笔记|第8节|大厂高并发缓存架构实战与优化

缓存架构 代码结构 代码详情 功能点&#xff1a; 多级缓存&#xff0c;先查本地缓存&#xff0c;再查Redis&#xff0c;最后才查数据库热点数据重建逻辑使用分布式锁&#xff0c;二次查询更新缓存采用读写锁提升性能采用Redis的发布订阅机制通知所有实例更新本地缓存适用读多…...

基于IDIG-GAN的小样本电机轴承故障诊断

目录 🔍 核心问题 一、IDIG-GAN模型原理 1. 整体架构 2. 核心创新点 (1) ​梯度归一化(Gradient Normalization)​​ (2) ​判别器梯度间隙正则化(Discriminator Gradient Gap Regularization)​​ (3) ​自注意力机制(Self-Attention)​​ 3. 完整损失函数 二…...

如何更改默认 Crontab 编辑器 ?

在 Linux 领域中&#xff0c;crontab 是您可能经常遇到的一个术语。这个实用程序在类 unix 操作系统上可用&#xff0c;用于调度在预定义时间和间隔自动执行的任务。这对管理员和高级用户非常有益&#xff0c;允许他们自动执行各种系统任务。 编辑 Crontab 文件通常使用文本编…...

什么是VR全景技术

VR全景技术&#xff0c;全称为虚拟现实全景技术&#xff0c;是通过计算机图像模拟生成三维空间中的虚拟世界&#xff0c;使用户能够在该虚拟世界中进行全方位、无死角的观察和交互的技术。VR全景技术模拟人在真实空间中的视觉体验&#xff0c;结合图文、3D、音视频等多媒体元素…...