Leetcode 2905. Find Indices With Index and Value Difference II

2023-10-16 03:28

本文主要是介绍Leetcode 2905. Find Indices With Index and Value Difference II,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

  • Leetcode 2905. Find Indices With Index and Value Difference II
    • 1. 解题思路
    • 2. 代码实现
  • 题目链接:2905. Find Indices With Index and Value Difference II

1. 解题思路

这一题我一开始思路有点想复杂了,因为这道题显然是要在index相距特定距离以上的前提下找一个绝对值相差大于给定值的数,因此,我们只需要简化问题直接找对应范围内的最大值或者最小值看它是否满足条件即可。

故而,这个问题事实上就变成了求特定范围内的最大值或者最小值,而这个问题可以直接套用Segment Tree的思路进行求解,关于Segment Tree,我之前写过一个简单的博客(经典算法:Segment Tree)进行过介绍,这里就不进行展开了。

但是,后来我们注意到,这个思路事实上有点做复杂了,因为我们需要求的这个范围事实上仅仅为某个坐标之后的最大值以及最小值,因此事实上完全可以当成一个累计数组的问题来进行求解,我们只需要遍历一下左边界(记作i),然后考察范围i+indexDifference右侧的最大和最小元素进行考察即可。

2. 代码实现

给出python代码实现如下:

class Solution:def findIndices(self, nums: List[int], indexDifference: int, valueDifference: int) -> List[int]:n = len(nums)maxs = [(x, i) for i, x in enumerate(nums)]mins = [(x, i) for i, x in enumerate(nums)]for i in range(n-2, -1, -1):maxs[i] = max(maxs[i], maxs[i+1])mins[i] = min(mins[i], mins[i+1])for i in range(n-indexDifference):val, idx = maxs[i+indexDifference]if abs(val - nums[i]) >= valueDifference:return [i, idx]val, idx = mins[i+indexDifference]if abs(val - nums[i]) >= valueDifference:return [i, idx]return [-1, -1]

提交代码评测得到:耗时852ms,占用内存42.9MB。

这篇关于Leetcode 2905. Find Indices With Index and Value Difference II的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/218692

相关文章

Java枚举类实现Key-Value映射的多种实现方式

《Java枚举类实现Key-Value映射的多种实现方式》在Java开发中,枚举(Enum)是一种特殊的类,本文将详细介绍Java枚举类实现key-value映射的多种方式,有需要的小伙伴可以根据需要... 目录前言一、基础实现方式1.1 为枚举添加属性和构造方法二、http://www.cppcns.co

如何解决mysql出现Incorrect string value for column ‘表项‘ at row 1错误问题

《如何解决mysql出现Incorrectstringvalueforcolumn‘表项‘atrow1错误问题》:本文主要介绍如何解决mysql出现Incorrectstringv... 目录mysql出现Incorrect string value for column ‘表项‘ at row 1错误报错

浅析CSS 中z - index属性的作用及在什么情况下会失效

《浅析CSS中z-index属性的作用及在什么情况下会失效》z-index属性用于控制元素的堆叠顺序,值越大,元素越显示在上层,它需要元素具有定位属性(如relative、absolute、fi... 目录1. z-index 属性的作用2. z-index 失效的情况2.1 元素没有定位属性2.2 元素处

Linux find 命令完全指南及核心用法

《Linuxfind命令完全指南及核心用法》find是Linux系统最强大的文件搜索工具,支持嵌套遍历、条件筛选、执行动作,下面给大家介绍Linuxfind命令完全指南,感兴趣的朋友一起看看吧... 目录一、基础搜索模式1. 按文件名搜索(精确/模糊匹配)2. 排除指定目录/文件二、根据文件类型筛选三、时间

哈希leetcode-1

目录 1前言 2.例题  2.1两数之和 2.2判断是否互为字符重排 2.3存在重复元素1 2.4存在重复元素2 2.5字母异位词分组 1前言 哈希表主要是适合于快速查找某个元素(O(1)) 当我们要频繁的查找某个元素,第一哈希表O(1),第二,二分O(log n) 一般可以分为语言自带的容器哈希和用数组模拟的简易哈希。 最简单的比如数组模拟字符存储,只要开26个c

AI基础 L9 Local Search II 局部搜索

Local Beam search 对于当前的所有k个状态,生成它们的所有可能后继状态。 检查生成的后继状态中是否有任何状态是解决方案。 如果所有后继状态都不是解决方案,则从所有后继状态中选择k个最佳状态。 当达到预设的迭代次数或满足某个终止条件时,算法停止。 — Choose k successors randomly, biased towards good ones — Close

leetcode-24Swap Nodes in Pairs

带头结点。 /*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) { val = x; }* }*/public class Solution {public ListNode swapPairs(L

leetcode-23Merge k Sorted Lists

带头结点。 /*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) { val = x; }* }*/public class Solution {public ListNode mergeKLists

C++ | Leetcode C++题解之第393题UTF-8编码验证

题目: 题解: class Solution {public:static const int MASK1 = 1 << 7;static const int MASK2 = (1 << 7) + (1 << 6);bool isValid(int num) {return (num & MASK2) == MASK1;}int getBytes(int num) {if ((num &

从0到1,AI我来了- (7)AI应用-ComfyUI-II(进阶)

上篇comfyUI 入门 ,了解了TA是个啥,这篇,我们通过ComfyUI 及其相关Lora 模型,生成一些更惊艳的图片。这篇主要了解这些内容:         1、哪里获取模型?         2、实践如何画一个美女?         3、附录:               1)相关SD(稳定扩散模型的组成部分)               2)模型放置目录(重要)