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 <= 1000 <= nums[i] <= 500 <= indexDifference <= 1000 <= 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。但是再问深入一点:它是干嘛的,它有什么用,可能就回答不出来了。 一方面没多少人研究和使用微前端。可能还没来得及用微前端扩展项目,公司就已经倒闭了。 另一方…...
浏览器访问 AWS ECS 上部署的 Docker 容器(监听 80 端口)
✅ 一、ECS 服务配置 Dockerfile 确保监听 80 端口 EXPOSE 80 CMD ["nginx", "-g", "daemon off;"]或 EXPOSE 80 CMD ["python3", "-m", "http.server", "80"]任务定义(Task Definition&…...
树莓派超全系列教程文档--(62)使用rpicam-app通过网络流式传输视频
使用rpicam-app通过网络流式传输视频 使用 rpicam-app 通过网络流式传输视频UDPTCPRTSPlibavGStreamerRTPlibcamerasrc GStreamer 元素 文章来源: http://raspberry.dns8844.cn/documentation 原文网址 使用 rpicam-app 通过网络流式传输视频 本节介绍来自 rpica…...
基于距离变化能量开销动态调整的WSN低功耗拓扑控制开销算法matlab仿真
目录 1.程序功能描述 2.测试软件版本以及运行结果展示 3.核心程序 4.算法仿真参数 5.算法理论概述 6.参考文献 7.完整程序 1.程序功能描述 通过动态调整节点通信的能量开销,平衡网络负载,延长WSN生命周期。具体通过建立基于距离的能量消耗模型&am…...
C++:std::is_convertible
C++标志库中提供is_convertible,可以测试一种类型是否可以转换为另一只类型: template <class From, class To> struct is_convertible; 使用举例: #include <iostream> #include <string>using namespace std;struct A { }; struct B : A { };int main…...
从深圳崛起的“机器之眼”:赴港乐动机器人的万亿赛道赶考路
进入2025年以来,尽管围绕人形机器人、具身智能等机器人赛道的质疑声不断,但全球市场热度依然高涨,入局者持续增加。 以国内市场为例,天眼查专业版数据显示,截至5月底,我国现存在业、存续状态的机器人相关企…...
【第二十一章 SDIO接口(SDIO)】
第二十一章 SDIO接口 目录 第二十一章 SDIO接口(SDIO) 1 SDIO 主要功能 2 SDIO 总线拓扑 3 SDIO 功能描述 3.1 SDIO 适配器 3.2 SDIOAHB 接口 4 卡功能描述 4.1 卡识别模式 4.2 卡复位 4.3 操作电压范围确认 4.4 卡识别过程 4.5 写数据块 4.6 读数据块 4.7 数据流…...
测试markdown--肇兴
day1: 1、去程:7:04 --11:32高铁 高铁右转上售票大厅2楼,穿过候车厅下一楼,上大巴车 ¥10/人 **2、到达:**12点多到达寨子,买门票,美团/抖音:¥78人 3、中饭&a…...
【CSS position 属性】static、relative、fixed、absolute 、sticky详细介绍,多层嵌套定位示例
文章目录 ★ position 的五种类型及基本用法 ★ 一、position 属性概述 二、position 的五种类型详解(初学者版) 1. static(默认值) 2. relative(相对定位) 3. absolute(绝对定位) 4. fixed(固定定位) 5. sticky(粘性定位) 三、定位元素的层级关系(z-i…...
【HTTP三个基础问题】
面试官您好!HTTP是超文本传输协议,是互联网上客户端和服务器之间传输超文本数据(比如文字、图片、音频、视频等)的核心协议,当前互联网应用最广泛的版本是HTTP1.1,它基于经典的C/S模型,也就是客…...
算法:模拟
1.替换所有的问号 1576. 替换所有的问号 - 力扣(LeetCode) 遍历字符串:通过外层循环逐一检查每个字符。遇到 ? 时处理: 内层循环遍历小写字母(a 到 z)。对每个字母检查是否满足: 与…...
