当前位置: 首页 > 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;公司就已经倒闭了。 另一方…...

Vue记事本应用实现教程

文章目录 1. 项目介绍2. 开发环境准备3. 设计应用界面4. 创建Vue实例和数据模型5. 实现记事本功能5.1 添加新记事项5.2 删除记事项5.3 清空所有记事 6. 添加样式7. 功能扩展&#xff1a;显示创建时间8. 功能扩展&#xff1a;记事项搜索9. 完整代码10. Vue知识点解析10.1 数据绑…...

基于Flask实现的医疗保险欺诈识别监测模型

基于Flask实现的医疗保险欺诈识别监测模型 项目截图 项目简介 社会医疗保险是国家通过立法形式强制实施&#xff0c;由雇主和个人按一定比例缴纳保险费&#xff0c;建立社会医疗保险基金&#xff0c;支付雇员医疗费用的一种医疗保险制度&#xff0c; 它是促进社会文明和进步的…...

ardupilot 开发环境eclipse 中import 缺少C++

目录 文章目录 目录摘要1.修复过程摘要 本节主要解决ardupilot 开发环境eclipse 中import 缺少C++,无法导入ardupilot代码,会引起查看不方便的问题。如下图所示 1.修复过程 0.安装ubuntu 软件中自带的eclipse 1.打开eclipse—Help—install new software 2.在 Work with中…...

用docker来安装部署freeswitch记录

今天刚才测试一个callcenter的项目&#xff0c;所以尝试安装freeswitch 1、使用轩辕镜像 - 中国开发者首选的专业 Docker 镜像加速服务平台 编辑下面/etc/docker/daemon.json文件为 {"registry-mirrors": ["https://docker.xuanyuan.me"] }同时可以进入轩…...

实现弹窗随键盘上移居中

实现弹窗随键盘上移的核心思路 在Android中&#xff0c;可以通过监听键盘的显示和隐藏事件&#xff0c;动态调整弹窗的位置。关键点在于获取键盘高度&#xff0c;并计算剩余屏幕空间以重新定位弹窗。 // 在Activity或Fragment中设置键盘监听 val rootView findViewById<V…...

Spring数据访问模块设计

前面我们已经完成了IoC和web模块的设计&#xff0c;聪明的码友立马就知道了&#xff0c;该到数据访问模块了&#xff0c;要不就这俩玩个6啊&#xff0c;查库势在必行&#xff0c;至此&#xff0c;它来了。 一、核心设计理念 1、痛点在哪 应用离不开数据&#xff08;数据库、No…...

GruntJS-前端自动化任务运行器从入门到实战

Grunt 完全指南&#xff1a;从入门到实战 一、Grunt 是什么&#xff1f; Grunt是一个基于 Node.js 的前端自动化任务运行器&#xff0c;主要用于自动化执行项目开发中重复性高的任务&#xff0c;例如文件压缩、代码编译、语法检查、单元测试、文件合并等。通过配置简洁的任务…...

Webpack性能优化:构建速度与体积优化策略

一、构建速度优化 1、​​升级Webpack和Node.js​​ ​​优化效果​​&#xff1a;Webpack 4比Webpack 3构建时间降低60%-98%。​​原因​​&#xff1a; V8引擎优化&#xff08;for of替代forEach、Map/Set替代Object&#xff09;。默认使用更快的md4哈希算法。AST直接从Loa…...

使用SSE解决获取状态不一致问题

使用SSE解决获取状态不一致问题 1. 问题描述2. SSE介绍2.1 SSE 的工作原理2.2 SSE 的事件格式规范2.3 SSE与其他技术对比2.4 SSE 的优缺点 3. 实战代码 1. 问题描述 目前做的一个功能是上传多个文件&#xff0c;这个上传文件是整体功能的一部分&#xff0c;文件在上传的过程中…...

【51单片机】4. 模块化编程与LCD1602Debug

1. 什么是模块化编程 传统编程会将所有函数放在main.c中&#xff0c;如果使用的模块多&#xff0c;一个文件内会有很多代码&#xff0c;不利于组织和管理 模块化编程则是将各个模块的代码放在不同的.c文件里&#xff0c;在.h文件里提供外部可调用函数声明&#xff0c;其他.c文…...