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。但是再问深入一点:它是干嘛的,它有什么用,可能就回答不出来了。 一方面没多少人研究和使用微前端。可能还没来得及用微前端扩展项目,公司就已经倒闭了。 另一方…...
web vue 项目 Docker化部署
Web 项目 Docker 化部署详细教程 目录 Web 项目 Docker 化部署概述Dockerfile 详解 构建阶段生产阶段 构建和运行 Docker 镜像 1. Web 项目 Docker 化部署概述 Docker 化部署的主要步骤分为以下几个阶段: 构建阶段(Build Stage):…...
mongodb源码分析session执行handleRequest命令find过程
mongo/transport/service_state_machine.cpp已经分析startSession创建ASIOSession过程,并且验证connection是否超过限制ASIOSession和connection是循环接受客户端命令,把数据流转换成Message,状态转变流程是:State::Created 》 St…...
2.Vue编写一个app
1.src中重要的组成 1.1main.ts // 引入createApp用于创建应用 import { createApp } from "vue"; // 引用App根组件 import App from ./App.vue;createApp(App).mount(#app)1.2 App.vue 其中要写三种标签 <template> <!--html--> </template>…...
Python爬虫(一):爬虫伪装
一、网站防爬机制概述 在当今互联网环境中,具有一定规模或盈利性质的网站几乎都实施了各种防爬措施。这些措施主要分为两大类: 身份验证机制:直接将未经授权的爬虫阻挡在外反爬技术体系:通过各种技术手段增加爬虫获取数据的难度…...
土地利用/土地覆盖遥感解译与基于CLUE模型未来变化情景预测;从基础到高级,涵盖ArcGIS数据处理、ENVI遥感解译与CLUE模型情景模拟等
🔍 土地利用/土地覆盖数据是生态、环境和气象等诸多领域模型的关键输入参数。通过遥感影像解译技术,可以精准获取历史或当前任何一个区域的土地利用/土地覆盖情况。这些数据不仅能够用于评估区域生态环境的变化趋势,还能有效评价重大生态工程…...
是否存在路径(FIFOBB算法)
题目描述 一个具有 n 个顶点e条边的无向图,该图顶点的编号依次为0到n-1且不存在顶点与自身相连的边。请使用FIFOBB算法编写程序,确定是否存在从顶点 source到顶点 destination的路径。 输入 第一行两个整数,分别表示n 和 e 的值(1…...
Web 架构之 CDN 加速原理与落地实践
文章目录 一、思维导图二、正文内容(一)CDN 基础概念1. 定义2. 组成部分 (二)CDN 加速原理1. 请求路由2. 内容缓存3. 内容更新 (三)CDN 落地实践1. 选择 CDN 服务商2. 配置 CDN3. 集成到 Web 架构 …...
如何在网页里填写 PDF 表格?
有时候,你可能希望用户能在你的网站上填写 PDF 表单。然而,这件事并不简单,因为 PDF 并不是一种原生的网页格式。虽然浏览器可以显示 PDF 文件,但原生并不支持编辑或填写它们。更糟的是,如果你想收集表单数据ÿ…...
Linux C语言网络编程详细入门教程:如何一步步实现TCP服务端与客户端通信
文章目录 Linux C语言网络编程详细入门教程:如何一步步实现TCP服务端与客户端通信前言一、网络通信基础概念二、服务端与客户端的完整流程图解三、每一步的详细讲解和代码示例1. 创建Socket(服务端和客户端都要)2. 绑定本地地址和端口&#x…...
PAN/FPN
import torch import torch.nn as nn import torch.nn.functional as F import mathclass LowResQueryHighResKVAttention(nn.Module):"""方案 1: 低分辨率特征 (Query) 查询高分辨率特征 (Key, Value).输出分辨率与低分辨率输入相同。"""def __…...
