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
  • -109 <= nums[i] <= 109
  • 0 <= target <= 2 * 109

解题思路

这是一个典型的动态规划问题，我们需要找到到达最后一个位置的最大跳跃次数。

核心思路：

定义 dp[i] 表示从位置 0 到达位置 i 的最大跳跃次数。如果无法到达位置 i，则 dp[i] = -1。

状态转移：

对于每个位置 j，我们遍历所有可能的起跳位置 i（i < j），如果满足跳跃条件 -target <= nums[j] - nums[i] <= target 且 dp[i] != -1，则可以从位置 i 跳到位置 j，此时 dp[j] = max(dp[j], dp[i] + 1)。

初始化：

  • dp[0] = 0，起始位置不需要跳跃
  • 其他位置初始化为 -1，表示暂时无法到达

算法流程：

  1. 初始化 dp 数组
  2. 对于每个位置 j，遍历所有可能的起跳位置 i
  3. 检查跳跃条件，更新 dp[j]
  4. 返回 dp[n-1]

时间复杂度为 O(n²)，适合题目的数据范围。

代码实现

class Solution {
public:
    int maximumJumps(vector<int>& nums, int target) {
        int n = nums.size();
        vector<int> dp(n, -1);
        dp[0] = 0;
        
        for (int j = 1; j < n; j++) {
            for (int i = 0; i < j; i++) {
                if (dp[i] != -1 && abs(nums[j] - nums[i]) <= target) {
                    dp[j] = max(dp[j], dp[i] + 1);
                }
            }
        }
        
        return dp[n - 1];
    }
};

class Solution:
    def maximumJumps(self, nums: List[int], target: int) -> int:
        n = len(nums)
        dp = [-1] * n
        dp[0] = 0
        
        for j in range(1, n):
            for i in range(j):
                if dp[i] != -1 and abs(nums[j] - nums[i]) <= target:
                    dp[j] = max(dp[j], dp[i] + 1)
        
        return dp[n - 1]

public class Solution {
    public int MaximumJumps(int[] nums, int target) {
        int n = nums.Length;
        int[] dp = new int[n];
        Array.Fill(dp, -1);
        dp[0] = 0;
        
        for (int j = 1; j < n; j++) {
            for (int i = 0; i < j; i++) {
                if (dp[i] != -1 && Math.Abs(nums[j] - nums[i]) <= target) {
                    dp[j] = Math.Max(dp[j], dp[i] + 1);
                }
            }
        }
        
        return dp[n - 1];
    }
}

var maximumJumps = function(nums, target) {
    const n = nums.length;
    const dp = new Array(n).fill(-1);
    dp[0] = 0;
    
    for (let j = 1; j < n; j++) {
        for (let i = 0; i < j; i++) {
            if (dp[i] !== -1 && Math.abs(nums[j] - nums[i]) <= target) {
                dp[j] = Math.max(dp[j], dp[i] + 1);
            }
        }
    }
    
    return dp[n - 1];
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n²)双重循环遍历所有位置对
空间复杂度O(n)需要额外的 dp 数组存储状态

相关题目