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 = 3 。
abs(0 - 3) >= 2 且 abs(nums[0] - nums[3]) >= 4 。
因此,[0,3] 是一个符合题目要求的答案。
[3,0] 也是符合题目要求的答案。
示例 2:
输入:nums = [2,1], indexDifference = 0, valueDifference = 0
输出:[0,0]
解释:
在示例中,可以选择 i = 0 和 j = 0 。
abs(0 - 0) >= 0 且 abs(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} i≤j−indexDifference 。
类似 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} mx−nums[j]≥valueDifference
- nums [ j ] − m n ≥ valueDifference \textit{nums}[j] - mn \ge \textit{valueDifference} nums[j]−mn≥valueDifference
代码实现时,可以维护最大值的下标 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} ∣mx−nums[j]∣≥valueDifference ,不就错过答案了吗?
答:不会的,如果出现这种情况,那么一定会有 nums [ j ] − m n ≥ valueDifference \textit{nums}[j] - mn \ge \textit{valueDifference} nums[j]−mn≥valueDifference 。
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」系列文章之一,这一系列正式开始于2021/08/12。由于LeetCode上部分题目有锁,本系列将至少持续到刷完所有无锁题之日为止;由于LeetCode还在不断地创建新题,本系列的终止日期可能是永远。在这一系列刷题文章…...
【神经网络】如何在Pytorch中从零开始将MNIST网络量化为8位
论文: Quantization and Training of Neural Networks for Efficient Integer-Arithmetic-Only Inference 下载地址:https://arxiv.org/pdf/1712.05877.pdf 更新:量化感知训练的博客文章是在线的,并在这里链接,通过它我们可以训…...

智慧水利:山海鲸数字孪生的革新之路
一、概念 什么是港口? "港口"通常指的是一个水域或岸边的设施,用于装载、卸载、储存和处理货物、以及提供与海上、河流或湖泊交通相关的服务。港口可以包括各种类型的码头、码头设备、仓库、货物运输设施、以及各种管理和物流设施。 什么是数…...

【unity】【VR】白马VR课堂系列-VR开发核心基础04-主体设置-XR Rig的引入和设置
接下来我们开始引入并构建XR Rig。 你可以将XR Rig理解为玩家在VR世界中的替身。 我们先删除Main Camera,在Hierarchy右键点击删除。 然后再在场景层右键选择XR下的XR Origin。这时一个XR Origin对象就被添加到了Hierarchy。 重设XR Origin的Position和Rotation…...

Arcgis实现Tiff合并
Arcgis实现Tiff合并 现有四幅Tiff影像 打开数据管理工具 输入使用这四幅影像 下面这个就是建立数据库,这个不对 点击确定 合成完毕...
将已有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(URL)参数 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为例进行数据盘挂载的操作演示,挂载一个200G盘 1、切换至root用户 z 2、查看要挂载的硬盘 执行sfdisk -s 或 fdisk -l可以看到有一个200G。 sfdisk -s fdisk -l 需要挂载200G的这块硬盘。 3、执行lvs查看当前的lvm信息 4、执行pvcreate /dev/sdb创建…...

网络安全——自学(黑客技术)
前言 前几天发布了一篇 网络安全(黑客)自学 没想到收到了许多人的私信想要学习网安黑客技术!却不知道从哪里开始学起!怎么学?如何学? 今天给大家分享一下,很多人上来就说想学习黑客,…...
Npm——yalc本地库调试工具
全局安装 npm i -g yalc本地库发布 yalc publish项目中安装 yalc add 库名本地库更新后推送 yalc push项目中删除库 yalc remove --all...

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

docker部署的jenkins配置(接口自动化)
目录 一、jenkins汉化1.点击Manage Jenkins(系统管理),点击Plugins(插件)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/可以在浏览器中点击下载,也可以使用命令行下载 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是职场必备技能,尤其在商务活动中,企业宣传、项目提案、路演宣讲……都需要用好PPT。然而,很多人的PPT效率低、效果差,客户不认可、老板不满意。 PPT不仅是办公软件,更是以汇报对象为中心、以共同的目标为导向、以…...
探究Socks5代理和代理IP在技术领域的多重应用
随着数字化时代的不断发展,网络工程师在跨界电商、爬虫数据采集、出海业务拓展以及游戏优化等领域扮演着关键角色。而Socks5代理和代理IP作为他们的得力工具,在这些领域中发挥着至关重要的作用。本文将深入探讨这两种技术在技术领域中的应用,…...
解决Vue2封装组件含有echarts时多次调用出现id重复问题
解决Vue2封装组件含有echarts时多次调用出现id重复问题 1、前言2、解决方法 1、前言 封装组件中使用echarts时,多次调用导致id重复,出现页面不渲染、数据覆盖等问题。 2、解决方法 把id改成动态传参(这里就不作代码展示了) 把i…...
IntelliJ IDEA 中 Maven 相关操作详解
在这篇文章中,我们将详细探讨 IntelliJ IDEA 中 Maven 的相关操作。我们将从以下三个角度进行讲解: IntelliJ IDEA 中 Maven 插件的 "Reimport All Maven Projects" 和 "Generate Sources and Update Folders For All Projects" 按…...

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

【微前端】single-spa 到底是个什么鬼
前言 说起微前端框架,很多人第一反应就是 single-spa。但是再问深入一点:它是干嘛的,它有什么用,可能就回答不出来了。 一方面没多少人研究和使用微前端。可能还没来得及用微前端扩展项目,公司就已经倒闭了。 另一方…...
Vue记事本应用实现教程
文章目录 1. 项目介绍2. 开发环境准备3. 设计应用界面4. 创建Vue实例和数据模型5. 实现记事本功能5.1 添加新记事项5.2 删除记事项5.3 清空所有记事 6. 添加样式7. 功能扩展:显示创建时间8. 功能扩展:记事项搜索9. 完整代码10. Vue知识点解析10.1 数据绑…...

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

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的项目,所以尝试安装freeswitch 1、使用轩辕镜像 - 中国开发者首选的专业 Docker 镜像加速服务平台 编辑下面/etc/docker/daemon.json文件为 {"registry-mirrors": ["https://docker.xuanyuan.me"] }同时可以进入轩…...
实现弹窗随键盘上移居中
实现弹窗随键盘上移的核心思路 在Android中,可以通过监听键盘的显示和隐藏事件,动态调整弹窗的位置。关键点在于获取键盘高度,并计算剩余屏幕空间以重新定位弹窗。 // 在Activity或Fragment中设置键盘监听 val rootView findViewById<V…...

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

GruntJS-前端自动化任务运行器从入门到实战
Grunt 完全指南:从入门到实战 一、Grunt 是什么? Grunt是一个基于 Node.js 的前端自动化任务运行器,主要用于自动化执行项目开发中重复性高的任务,例如文件压缩、代码编译、语法检查、单元测试、文件合并等。通过配置简洁的任务…...
Webpack性能优化:构建速度与体积优化策略
一、构建速度优化 1、升级Webpack和Node.js 优化效果:Webpack 4比Webpack 3构建时间降低60%-98%。原因: V8引擎优化(for of替代forEach、Map/Set替代Object)。默认使用更快的md4哈希算法。AST直接从Loa…...

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

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