达到末尾下标所需的最大跳跃次数

难度: Medium

给你一个下标从 0 开始、由 n 个整数组成的数组 nums 和一个整数 target 。

你的初始位置在下标 0 。在一步操作中，你可以从下标 i 跳跃到任意满足下述条件的下标 j ：

0 <= i < j < n
-target <= nums[j] - nums[i] <= target

返回到达下标 n - 1 处所需的 最大跳跃次数 。

如果无法到达下标 n - 1 ，返回 -1 。

示例 1：

输入：nums = [1,3,6,4,1,2], target = 2
输出：3
解释：要想以最大跳跃次数从下标 0 到下标 n - 1 ，可以按下述跳跃序列执行操作：
- 从下标 0 跳跃到下标 1 。 
- 从下标 1 跳跃到下标 3 。 
- 从下标 3 跳跃到下标 5 。 
可以证明，从 0 到 n - 1 的所有方案中，不存在比 3 步更长的跳跃序列。因此，答案是 3 。

示例 2：

输入：nums = [1,3,6,4,1,2], target = 3
输出：5
解释：要想以最大跳跃次数从下标 0 到下标 n - 1 ，可以按下述跳跃序列执行操作：
- 从下标 0 跳跃到下标 1 。 
- 从下标 1 跳跃到下标 2 。 
- 从下标 2 跳跃到下标 3 。 
- 从下标 3 跳跃到下标 4 。 
- 从下标 4 跳跃到下标 5 。 
可以证明，从 0 到 n - 1 的所有方案中，不存在比 5 步更长的跳跃序列。因此，答案是 5 。

示例 3：

输入：nums = [1,3,6,4,1,2], target = 0
输出：-1
解释：可以证明不存在从 0 到 n - 1 的跳跃序列。因此，答案是 -1 。

提示：

2 <= nums.length == n <= 1000
-10⁹ <= nums[i] <= 10⁹
0 <= target <= 2 * 10⁹

Submission

运行时间: 263 ms

内存: 16.9 MB

inf = 1<<60
class ZKW:
    """自低向上非递归写法线段树，0_indexed
    tmx = ZKW(pre, max, -2 ** 61)
    """
    __slots__ = ('n', 'op', 'e', 'log', 'size', 'd')

    def __init__(self, n, OP, E):
        """
        OP: 操作:max,min,sum
        E: 每个元素默认值
        """
        self.n = n
        self.op = OP
        self.e = E
        self.log = (self.n - 1).bit_length()
        self.size = 1 << self.log
        self.d = [E for i in range(2 * self.size)]

    def build(self, V):
        for i in range(self.n):
            self.d[self.size+i]=V[i]
        for i in range(self.size-1,0,-1):
            self.update(i)

    def set(self, p, x):
        # assert 0 <= p and p < self.n
        update = self.update
        p += self.size
        self.d[p] = x
        for i in range(1, self.log + 1):
            update(p >> i)
            
    def get(self,p):
        p+=self.size
        return self.d[p]

    def query(self, l, r):  # [l,r] 双闭区间
        # assert 0 <= l and l <= r and r <= self.n
        sml, smr, op, d = self.e, self.e, self.op, self.d
        l += self.size
        r += self.size+1
        while l < r:
            if l & 1:
                sml = op(sml, d[l])
                l += 1
            if r & 1:
                smr = op(d[r - 1], smr)
                r -= 1
            l >>= 1
            r >>= 1
        return self.op(sml, smr)

    def update(self, k):
        self.d[k] = self.op(self.d[2 * k], self.d[2 * k + 1])
    def all_query(self):
        return self.d[1]
class Solution:
    def maximumJumps(self, nums: List[int], target: int) -> int:
        arr=[]
        for i in nums:
            arr+=[i-target,i,i+target]
        arr=sorted(set(arr))
        d={x:i for i,x in enumerate(arr)}
        seg=ZKW(len(d),max,-inf)
        seg.set(d[nums[0]],0)
        n=len(nums)
        for i in range(1,n):
            x=nums[i]
            q=seg.query(d[x-target],d[x+target])
            seg.set(d[x],q+1)
            if i==n-1:
                if q<0:
                    return -1
                else:
                    return q+1

Explain

该题解采用了线段树（ZKW线段树的非递归版本）来求解问题。首先，为了应对题目中允许的跳跃范围 [-target, target]，题解将数组中的每个元素 x 扩展到三个可能的跳跃值 x-target, x, x+target，并去重排序。这种扩展允许在 O(log n) 时间内查询和更新任何区间的最大值。通过映射每个扩展值到其索引，可以用线段树高效查询和更新最大的跳跃次数。遍历 nums 数组，对于每个元素 x，查询在 [x-target, x+target] 范围内的最大跳跃次数，并在线段树中更新当前 x 的位置。最后，检查是否能到达 n-1 索引处，并返回相应的跳跃次数。如果不能到达，则返回 -1。

时间复杂度: O(n log n)

空间复杂度: O(n)

inf = 1<<60
class ZKW:
    \"\"\"自低向上非递归写法线段树，0_indexed
    tmx = ZKW(pre, max, -2 ** 61)
    \"\"\"
    __slots__ = ('n', 'op', 'e', 'log', 'size', 'd')

    def __init__(self, n, OP, E):
        \"\"\"初始化线段树
        OP: 操作:max,min,sum
        E: 每个元素默认值
        \"\"\"
        self.n = n
        self.op = OP
        self.e = E
        self.log = (self.n - 1).bit_length()
        self.size = 1 << self.log
        self.d = [E for i in range(2 * self.size)]

    def build(self, V):
        for i in range(self.n):
            self.d[self.size+i]=V[i]
        for i in range(self.size-1,0,-1):
            self.update(i)

    def set(self, p, x):
        update = self.update
        p += self.size
        self.d[p] = x
        for i in range(1, self.log + 1):
            update(p >> i)
            
    def get(self,p):
        p+=self.size
        return self.d[p]

    def query(self, l, r):  # [l,r] 双闭区间
        sml, smr, op, d = self.e, self.e, self.op, self.d
        l += self.size
        r += self.size+1
        while l < r:
            if l & 1:
                sml = op(sml, d[l])
                l += 1
            if r & 1:
                smr = op(d[r - 1], smr)
                r -= 1
            l >>= 1
            r >>= 1
        return self.op(sml, smr)

    def update(self, k):
        self.d[k] = self.op(self.d[2 * k], self.d[2 * k + 1])
    def all_query(self):
        return self.d[1]
class Solution:
    def maximumJumps(self, nums: List[int], target: int) -> int:
        arr=[]
        for i in nums:
            arr+=[i-target,i,i+target]
        arr=sorted(set(arr))
        d={x:i for i,x in enumerate(arr)}
        seg=ZKW(len(d),max,-inf)
        seg.set(d[nums[0]],0)
        n=len(nums)
        for i in range(1,n):
            x=nums[i]
            q=seg.query(d[x-target],d[x+target])
            seg.set(d[x],q+1)
            if i==n-1:
                if q<0:
                    return -1
                else:
                    return q+1

Explore

在处理跳跃范围时，选择将每个元素扩展为 x-target, x, x+target 是为了覆盖所有可能的跳跃目的地。这样做可以确保算法能够考虑到从当前位置可能到达的所有位置。这种设计使得算法能够在更新和查询操作中直接访问到任意跳跃的目的地，极大地提高了效率。同时，这种方法需要更多的空间来存储扩展后的值，并且需要额外的计算来处理这些值，但这是为了确保算法的正确性和全面性。

ZKW线段树的非递归版本是一种自底向上的更新方法，不需要使用递归调用。在这种实现中，数组的元素首先被放置在线段树的底部，对应于叶子节点。对于更新操作，首先更新叶子节点，然后向上更新其祖先节点直到根节点。对于查询操作，从底层开始，逐层向上，根据查询区间的边界动态决定查询路径，合并左右子区间的结果。这种方式避免了递归造成的额外开销，提高了效率。

将每个元素的默认值设为 -inf 是为了正确处理还未经过更新的线段树节点。因为本题需要计算最大跳跃次数，未更新的节点应该不对最终结果产生影响（即被视为负无穷大，在求最大值时被忽略）。这样在进行区间最大值查询时，只有那些已经被设置或更新过的节点才会对结果有贡献，确保算法的正确性和初始状态的一致性。

如果最终的跳跃次数 q 为负值，意味着在尝试跳跃到最后一个索引的过程中，不存在有效的跳跃路径可以到达该索引。这通常发生在没有任何可用跳跃能够到达最后一个位置时，例如，如果前面所有的跳跃都不能覆盖到达最后位置的范围。在这种情况下，线段树查询返回的是初始化的 -inf 值，表明从起始点到终点无有效路径，因此算法返回 -1 来表示无法完成任务。