Hard

题目描述

给你一个整数数组 arr 和一个整数 d。每一步你可以从下标 i 跳到：

  • i + x，其中 i + x < arr.length 且 0 < x <= d
  • i - x，其中 i - x >= 0 且 0 < x <= d

除此以外，你从下标 i 跳到下标 j 需要满足：arr[i] > arr[j] 且 arr[i] > arr[k]，其中下标 k 是所有 i 到 j 之间的数字（更正式的，min(i, j) < k < max(i, j)）。

你可以选择数组的任意下标开始跳跃。请你返回你 最多 可以访问多少个下标。

请注意，任何时候你都不能跳到数组的外面。

示例 1：

输入：arr = [6,4,14,6,8,13,9,7,10,6,12], d = 2
输出：4
解释：你可以从下标 10 开始跳跃。你可以按照 10 --> 8 --> 6 --> 7 的顺序跳跃。
注意，如果你从下标 6 开始，你只能跳到下标 7 处。你不能跳到下标 5 处因为 13 > 9。你也不能跳到下标 4 处，因为下标 5 在下标 4 和 6 之间且 13 > 9。
类似的，你不能从下标 3 跳到下标 2 或者下标 1。

示例 2：

输入：arr = [3,3,3,3,3], d = 3
输出：1
解释：你可以从任意下标开始，但是你无法跳到任何其他下标。

示例 3：

输入：arr = [7,6,5,4,3,2,1], d = 1
输出：7
解释：从下标 0 开始，你可以按照 0 --> 1 --> 2 --> 3 --> 4 --> 5 --> 6 的顺序访问所有下标。

提示：

  • 1 <= arr.length <= 1000
  • 1 <= arr[i] <= 10^5
  • 1 <= d <= arr.length

解题思路

这是一个动态规划问题，关键在于理解跳跃的规则和设计合适的状态转移。

核心思路：

  1. 定义 dp[i] 表示从位置 i 开始能访问的最大位置数
  2. 从位置 i 可以跳到位置 j 的条件：
    • 距离满足：|i - j| <= d 且 |i - j| > 0
    • 高度满足：arr[i] > arr[j]
    • 路径无阻挡：i 到 j 之间的所有位置 k 都满足 arr[i] > arr[k]

解法选择：

  1. 记忆化搜索（推荐）：自顶向下，思路清晰，处理依赖关系自然
  2. 拓扑排序 + DP：将问题转化为DAG上的最长路径
  3. 按高度排序 + DP：先处理矮的位置，保证依赖关系

实现细节：

  • 使用记忆化避免重复计算
  • 对于每个位置，检查所有可能的跳跃目标
  • 验证跳跃路径上没有比起点更高或相等的位置阻挡

时间复杂度主要来自于每个位置需要检查 O(d) 个可能的跳跃目标，每次检查路径需要 O(d) 时间。

代码实现

class Solution {
public:
    int maxJumps(vector<int>& arr, int d) {
        int n = arr.size();
        vector<int> dp(n, -1);
        
        function<int(int)> dfs = [&](int i) -> int {
            if (dp[i] != -1) return dp[i];
            
            dp[i] = 1;
            
            // 向右跳
            for (int j = i + 1; j <= min(i + d, n - 1); j++) {
                if (arr[j] >= arr[i]) break;
                dp[i] = max(dp[i], 1 + dfs(j));
            }
            
            // 向左跳
            for (int j = i - 1; j >= max(i - d, 0); j--) {
                if (arr[j] >= arr[i]) break;
                dp[i] = max(dp[i], 1 + dfs(j));
            }
            
            return dp[i];
        };
        
        int result = 0;
        for (int i = 0; i < n; i++) {
            result = max(result, dfs(i));
        }
        
        return result;
    }
};

class Solution:
    def maxJumps(self, arr: List[int], d: int) -> int:
        n = len(arr)
        dp = [-1] * n
        
        def dfs(i):
            if dp[i] != -1:
                return dp[i]
            
            dp[i] = 1
            
            # 向右跳
            for j in range(i + 1, min(i + d + 1, n)):
                if arr[j] >= arr[i]:
                    break
                dp[i] = max(dp[i], 1 + dfs(j))
            
            # 向左跳
            for j in range(i - 1, max(i - d - 1, -1), -1):
                if arr[j] >= arr[i]:
                    break
                dp[i] = max(dp[i], 1 + dfs(j))
            
            return dp[i]
        
        result = 0
        for i in range(n):
            result = max(result, dfs(i))
        
        return result

public class Solution {
    public int MaxJumps(int[] arr, int d) {
        int n = arr.Length;
        int[] dp = new int[n];
        Array.Fill(dp, -1);
        
        int Dfs(int i) {
            if (dp[i] != -1) return dp[i];
            
            dp[i] = 1;
            
            // 向右跳
            for (int j = i + 1; j <= Math.Min(i + d, n - 1); j++) {
                if (arr[j] >= arr[i]) break;
                dp[i] = Math.Max(dp[i], 1 + Dfs(j));
            }
            
            // 向左跳
            for (int j = i - 1; j >= Math.Max(i - d, 0); j--) {
                if (arr[j] >= arr[i]) break;
                dp[i] = Math.Max(dp[i], 1 + Dfs(j));
            }
            
            return dp[i];
        }
        
        int result = 0;
        for (int i = 0; i < n; i++) {
            result = Math.Max(result, Dfs(i));
        }
        
        return result;
    }
}

var maxJumps = function(arr, d) {
    const n = arr.length;
    const dp = new Array(n).fill(-1);
    
    const dfs = (i) => {
        if (dp[i] !== -1) return dp[i];
        
        dp[i] = 1;
        
        // 向右跳
        for (let j = i + 1; j <= Math.min(i + d, n - 1); j++) {
            if (arr[j] >= arr[i]) break;
            dp[i] = Math.max(dp[i], 1 + dfs(j));
        }
        
        // 向左跳
        for (let j = i - 1; j >= Math.max(i - d, 0); j--) {
            if (arr[j] >= arr[i]) break;
            dp[i] = Math.max(dp[i], 1 + dfs(j));
        }
        
        return dp[i];
    };
    
    let result = 0;
    for (let i = 0; i < n; i++) {
        result = Math.max(result, dfs(i));
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n × d)每个位置最多被访问一次，每次访问需要检查最多2d个相邻位置
空间复杂度O(n)记忆化数组和递归栈空间

相关题目