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

LeetCode 2903. 找出满足差值条件的下标 I【双指针+维护最大最小】简单

本文属于「征服LeetCode」系列文章之一,这一系列正式开始于2021/08/12。由于LeetCode上部分题目有锁,本系列将至少持续到刷完所有无锁题之日为止;由于LeetCode还在不断地创建新题,本系列的终止日期可能是永远。在这一系列刷题文章中,我不仅会讲解多种解题思路及其优化,还会用多种编程语言实现题解,涉及到通用解法时更将归纳总结出相应的算法模板。

为了方便在PC上运行调试、分享代码文件,我还建立了相关的仓库:https://github.com/memcpy0/LeetCode-Conquest。在这一仓库中,你不仅可以看到LeetCode原题链接、题解代码、题解文章链接、同类题目归纳、通用解法总结等,还可以看到原题出现频率和相关企业等重要信息。如果有其他优选题解,还可以一同分享给他人。

由于本系列文章的内容随时可能发生更新变动,欢迎关注和收藏征服LeetCode系列文章目录一文以作备忘。

给你一个下标从 0 开始、长度为 n 的整数数组 nums ,以及整数 indexDifference 和整数 valueDifference 。

你的任务是从范围 [0, n - 1] 内找出  2 个满足下述所有条件的下标 i 和 j :

  • abs(i - j) >= indexDifference 且
  • abs(nums[i] - nums[j]) >= valueDifference

返回整数数组 answer。如果存在满足题目要求的两个下标,则 answer = [i, j] ;否则,answer = [-1, -1] 。如果存在多组可供选择的下标对,只需要返回其中任意一组即可。

注意:i 和 j 可能 相等 。

示例 1:

输入:nums = [5,1,4,1], indexDifference = 2, valueDifference = 4
输出:[0,3]
解释:在示例中,可以选择 i = 0 和 j = 3abs(0 - 3) >= 2abs(nums[0] - nums[3]) >= 4 。
因此,[0,3] 是一个符合题目要求的答案。
[3,0] 也是符合题目要求的答案。

示例 2:

输入:nums = [2,1], indexDifference = 0, valueDifference = 0
输出:[0,0]
解释:
在示例中,可以选择 i = 0 和 j = 0abs(0 - 0) >= 0abs(nums[0] - nums[0]) >= 0 。 
因此,[0,0] 是一个符合题目要求的答案。 
[0,1][1,0][1,1] 也是符合题目要求的答案。 

示例 3:

输入:nums = [1,2,3], indexDifference = 2, valueDifference = 4
输出:[-1,-1]
解释:在示例中,可以证明无法找出 2 个满足所有条件的下标。
因此,返回 [-1,-1]

提示:

  • 1 <= n == nums.length <= 100
  • 0 <= nums[i] <= 50
  • 0 <= indexDifference <= 100
  • 0 <= valueDifference <= 50

解法 双指针+维护最大最小

不妨设 i ≤ j − indexDifference i\le j - \textit{indexDifference} ijindexDifference

类似 121. 买卖股票的最佳时机,我们可以在枚举 j j j 的同时,维护 nums [ i ] \textit{nums}[i] nums[i] 的最大值 mx \textit{mx} mx 和最小值 mn \textit{mn} mn 。那么只要满足下面两个条件中的一个,就可以返回答案了。

  • mx − nums [ j ] ≥ valueDifference \textit{mx} -\textit{nums}[j] \ge \textit{valueDifference} mxnums[j]valueDifference
  • nums [ j ] − m n ≥ valueDifference \textit{nums}[j] - mn \ge \textit{valueDifference} nums[j]mnvalueDifference

代码实现时,可以维护最大值的下标 maxIdx \textit{maxIdx} maxIdx 和最小值的下标 minIdx \textit{minIdx} minIdx

问:为什么不用算绝对值?如果 mx < nums [ j ] \textit{mx} < \textit{nums}[j] mx<nums[j] 并且 ∣ mx − nums [ j ] ∣ ≥ valueDifference |\textit{mx} - \textit{nums}[j]| \ge \textit{valueDifference} mxnums[j]valueDifference ,不就错过答案了吗?
答:不会的,如果出现这种情况,那么一定会有 nums [ j ] − m n ≥ valueDifference \textit{nums}[j] - mn \ge \textit{valueDifference} nums[j]mnvalueDifference

class Solution {
public:vector<int> findIndices(vector<int>& nums, int indexDifference, int valueDifference) {int maxIdx = 0, minIdx = 0;for (int j = indexDifference; j < nums.size(); ++j) {int i = j - indexDifference;if (nums[i] > nums[maxIdx]) maxIdx = i;else if (nums[i] < nums[minIdx]) minIdx = i;if (nums[maxIdx] - nums[j] >= valueDifference) return {maxIdx, j};if (nums[j] - nums[minIdx] >= valueDifference) return {minIdx, j};}return {-1, -1};}
};

复杂度分析:

  • 时间复杂度: O ( n ) \mathcal{O}(n) O(n) ,其中 n n n nums \textit{nums} nums 的长度。
  • 空间复杂度: O ( 1 ) \mathcal{O}(1) O(1)

相关文章:

LeetCode 2903. 找出满足差值条件的下标 I【双指针+维护最大最小】简单

本文属于「征服LeetCode」系列文章之一&#xff0c;这一系列正式开始于2021/08/12。由于LeetCode上部分题目有锁&#xff0c;本系列将至少持续到刷完所有无锁题之日为止&#xff1b;由于LeetCode还在不断地创建新题&#xff0c;本系列的终止日期可能是永远。在这一系列刷题文章…...

【神经网络】如何在Pytorch中从零开始将MNIST网络量化为8位

论文&#xff1a; Quantization and Training of Neural Networks for Efficient Integer-Arithmetic-Only Inference 下载地址&#xff1a;https://arxiv.org/pdf/1712.05877.pdf 更新:量化感知训练的博客文章是在线的&#xff0c;并在这里链接&#xff0c;通过它我们可以训…...

智慧水利:山海鲸数字孪生的革新之路

一、概念 什么是港口&#xff1f; "港口"通常指的是一个水域或岸边的设施&#xff0c;用于装载、卸载、储存和处理货物、以及提供与海上、河流或湖泊交通相关的服务。港口可以包括各种类型的码头、码头设备、仓库、货物运输设施、以及各种管理和物流设施。 什么是数…...

【unity】【VR】白马VR课堂系列-VR开发核心基础04-主体设置-XR Rig的引入和设置

接下来我们开始引入并构建XR Rig。 你可以将XR Rig理解为玩家在VR世界中的替身。 我们先删除Main Camera&#xff0c;在Hierarchy右键点击删除。 然后再在场景层右键选择XR下的XR Origin。这时一个XR Origin对象就被添加到了Hierarchy。 重设XR Origin的Position和Rotation…...

Arcgis实现Tiff合并

Arcgis实现Tiff合并 现有四幅Tiff影像 打开数据管理工具 输入使用这四幅影像 下面这个就是建立数据库&#xff0c;这个不对 点击确定 合成完毕...

将已有jar包放进maven仓库

mvn install:install-file -DfileD:\sapjco3.jar -DgroupIdcom.sap.conn.jco -DartifactIdsapjco3 -Dversion3.0.14 -Dpackagingjar...

从0开始学go第八天

gin获取URL路径参数 package main//获取path&#xff08;URL&#xff09;参数 import ("net/http""github.com/gin-gonic/gin" )func main() {r : gin.Default()r.GET("/:name/:age", func(c *gin.Context) {//获取路径参数name : c.Param(&quo…...

centos7为例进行数据盘挂载详解

以centos7为例进行数据盘挂载的操作演示&#xff0c;挂载一个200G盘 1、切换至root用户 z 2、查看要挂载的硬盘 执行sfdisk -s 或 fdisk -l可以看到有一个200G。 sfdisk -s fdisk -l 需要挂载200G的这块硬盘。 3、执行lvs查看当前的lvm信息 4、执行pvcreate /dev/sdb创建…...

网络安全——自学(黑客技术)

前言 前几天发布了一篇 网络安全&#xff08;黑客&#xff09;自学 没想到收到了许多人的私信想要学习网安黑客技术&#xff01;却不知道从哪里开始学起&#xff01;怎么学&#xff1f;如何学&#xff1f; 今天给大家分享一下&#xff0c;很多人上来就说想学习黑客&#xff0c…...

Npm——yalc本地库调试工具

全局安装 npm i -g yalc本地库发布 yalc publish项目中安装 yalc add 库名本地库更新后推送 yalc push项目中删除库 yalc remove --all...

【Java基础面试一】、为什么Java代码可以实现一次编写、到处运行?

文章底部有个人公众号&#xff1a;热爱技术的小郑。主要分享开发知识、学习资料、毕业设计指导等。有兴趣的可以关注一下。为何分享&#xff1f; 踩过的坑没必要让别人在再踩&#xff0c;自己复盘也能加深记忆。利己利人、所谓双赢。 面试官&#xff1a;为什么Java代码可以实现…...

docker部署的jenkins配置(接口自动化)

目录 一、jenkins汉化1.点击Manage Jenkins&#xff08;系统管理&#xff09;&#xff0c;点击Plugins&#xff08;插件&#xff09;2.安装Locale插件 二、jenkins配置allure报告1.安装allure插件2.配置 三、配置jenkins项目1.新建任务2.创建项目3.源码管理4.构建触发器5.增加构…...

qemu 运行 linux

文章目录 qemu 运行 linuxlinux 内核版本生成配置文件编译设备树编译内核报错与解决运行 linux附录脚本参考 qemu 运行 linux linux 内核版本 linux-6.5.7linux 内核下载地址 https://www.kernel.org/可以在浏览器中点击下载&#xff0c;也可以使用命令行下载 wget https:/…...

线程安全问题 的小案例

package Thread_api_test;public class ThreadSafety {//模拟线程安全问题public static void main(String[] args) {//1:创建一个账户对象 代表两个人的共享账户Account accnew Account("ICBC",10000);//创建两个线程 分别两个人 再去同一个账户里取钱10000new Draw…...

高效PPT制作与演示技巧大揭秘

PPT是职场必备技能&#xff0c;尤其在商务活动中&#xff0c;企业宣传、项目提案、路演宣讲……都需要用好PPT。然而&#xff0c;很多人的PPT效率低、效果差&#xff0c;客户不认可、老板不满意。 PPT不仅是办公软件&#xff0c;更是以汇报对象为中心、以共同的目标为导向、以…...

探究Socks5代理和代理IP在技术领域的多重应用

随着数字化时代的不断发展&#xff0c;网络工程师在跨界电商、爬虫数据采集、出海业务拓展以及游戏优化等领域扮演着关键角色。而Socks5代理和代理IP作为他们的得力工具&#xff0c;在这些领域中发挥着至关重要的作用。本文将深入探讨这两种技术在技术领域中的应用&#xff0c;…...

解决Vue2封装组件含有echarts时多次调用出现id重复问题

解决Vue2封装组件含有echarts时多次调用出现id重复问题 1、前言2、解决方法 1、前言 封装组件中使用echarts时&#xff0c;多次调用导致id重复&#xff0c;出现页面不渲染、数据覆盖等问题。 2、解决方法 把id改成动态传参&#xff08;这里就不作代码展示了&#xff09; 把i…...

IntelliJ IDEA 中 Maven 相关操作详解

在这篇文章中&#xff0c;我们将详细探讨 IntelliJ IDEA 中 Maven 的相关操作。我们将从以下三个角度进行讲解&#xff1a; IntelliJ IDEA 中 Maven 插件的 "Reimport All Maven Projects" 和 "Generate Sources and Update Folders For All Projects" 按…...

3分钟,快速上手Postman接口测试!

Postman是一个用于调试HTTP请求的工具&#xff0c;它提供了友好的界面帮助分析、构造HTTP请求&#xff0c;并分析响应数据。实际工作中&#xff0c;开发和测试基本上都有使用Postman来进行接口调试工作。有一些其他流程的工具&#xff0c;也是模仿的Postman的风格进行接口测试工…...

【微前端】single-spa 到底是个什么鬼

前言 说起微前端框架&#xff0c;很多人第一反应就是 single-spa。但是再问深入一点&#xff1a;它是干嘛的&#xff0c;它有什么用&#xff0c;可能就回答不出来了。 一方面没多少人研究和使用微前端。可能还没来得及用微前端扩展项目&#xff0c;公司就已经倒闭了。 另一方…...

《Qt C++ 与 OpenCV:解锁视频播放程序设计的奥秘》

引言:探索视频播放程序设计之旅 在当今数字化时代,多媒体应用已渗透到我们生活的方方面面,从日常的视频娱乐到专业的视频监控、视频会议系统,视频播放程序作为多媒体应用的核心组成部分,扮演着至关重要的角色。无论是在个人电脑、移动设备还是智能电视等平台上,用户都期望…...

【2025年】解决Burpsuite抓不到https包的问题

环境&#xff1a;windows11 burpsuite:2025.5 在抓取https网站时&#xff0c;burpsuite抓取不到https数据包&#xff0c;只显示&#xff1a; 解决该问题只需如下三个步骤&#xff1a; 1、浏览器中访问 http://burp 2、下载 CA certificate 证书 3、在设置--隐私与安全--…...

selenium学习实战【Python爬虫】

selenium学习实战【Python爬虫】 文章目录 selenium学习实战【Python爬虫】一、声明二、学习目标三、安装依赖3.1 安装selenium库3.2 安装浏览器驱动3.2.1 查看Edge版本3.2.2 驱动安装 四、代码讲解4.1 配置浏览器4.2 加载更多4.3 寻找内容4.4 完整代码 五、报告文件爬取5.1 提…...

企业如何增强终端安全?

在数字化转型加速的今天&#xff0c;企业的业务运行越来越依赖于终端设备。从员工的笔记本电脑、智能手机&#xff0c;到工厂里的物联网设备、智能传感器&#xff0c;这些终端构成了企业与外部世界连接的 “神经末梢”。然而&#xff0c;随着远程办公的常态化和设备接入的爆炸式…...

【从零学习JVM|第三篇】类的生命周期(高频面试题)

前言&#xff1a; 在Java编程中&#xff0c;类的生命周期是指类从被加载到内存中开始&#xff0c;到被卸载出内存为止的整个过程。了解类的生命周期对于理解Java程序的运行机制以及性能优化非常重要。本文会深入探寻类的生命周期&#xff0c;让读者对此有深刻印象。 目录 ​…...

DingDing机器人群消息推送

文章目录 1 新建机器人2 API文档说明3 代码编写 1 新建机器人 点击群设置 下滑到群管理的机器人&#xff0c;点击进入 添加机器人 选择自定义Webhook服务 点击添加 设置安全设置&#xff0c;详见说明文档 成功后&#xff0c;记录Webhook 2 API文档说明 点击设置说明 查看自…...

MySQL:分区的基本使用

目录 一、什么是分区二、有什么作用三、分类四、创建分区五、删除分区 一、什么是分区 MySQL 分区&#xff08;Partitioning&#xff09;是一种将单张表的数据逻辑上拆分成多个物理部分的技术。这些物理部分&#xff08;分区&#xff09;可以独立存储、管理和优化&#xff0c;…...

如何应对敏捷转型中的团队阻力

应对敏捷转型中的团队阻力需要明确沟通敏捷转型目的、提升团队参与感、提供充分的培训与支持、逐步推进敏捷实践、建立清晰的奖励和反馈机制。其中&#xff0c;明确沟通敏捷转型目的尤为关键&#xff0c;团队成员只有清晰理解转型背后的原因和利益&#xff0c;才能降低对变化的…...

鸿蒙(HarmonyOS5)实现跳一跳小游戏

下面我将介绍如何使用鸿蒙的ArkUI框架&#xff0c;实现一个简单的跳一跳小游戏。 1. 项目结构 src/main/ets/ ├── MainAbility │ ├── pages │ │ ├── Index.ets // 主页面 │ │ └── GamePage.ets // 游戏页面 │ └── model │ …...

高分辨率图像合成归一化流扩展

大家读完觉得有帮助记得关注和点赞&#xff01;&#xff01;&#xff01; 1 摘要 我们提出了STARFlow&#xff0c;一种基于归一化流的可扩展生成模型&#xff0c;它在高分辨率图像合成方面取得了强大的性能。STARFlow的主要构建块是Transformer自回归流&#xff08;TARFlow&am…...