题目描述
给你一个整数数组 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 处开始，你可以按照数值从大到小，访问所有的下标。示例 4：
输入：arr = [7,1,7,1,7,1], d = 2
输出：2示例 5：
输入：arr = [66], d = 1
输出：1提示：
1 <= arr.length <= 10001 <= arr[i] <= 10^51 <= d <= arr.length
问题分析
这道题是跳跃游戏系列的第五题，有以下特点：
- 跳跃规则：
- 可以向左或向右跳跃，跳跃距离范围是 [1, d]
- 只能从高处往低处跳（arr[i] > arr[j]）
- 跳跃路径上的所有点都必须比起点低（arr[i] > arr[k]，对于所有 i 到 j 之间的 k）
- 目标：找出从任意起点出发，最多可以访问多少个下标。
- 关键点：
- 可以从任意下标开始
- 需要计算的是最大访问点数，而不是是否能到达某个特定目标
这个问题适合使用动态规划来解决，因为跳跃决策具有重叠子问题的性质。同时，由于跳跃的方向性（只能从高处跳到低处），我们可以按高度排序来确定解决问题的顺序。
解题思路
动态规划 + 记忆化搜索
我们可以定义 dp[i] 表示从下标 i 开始跳跃，最多可以访问的下标数量（包括起点自身）。
递推关系如下：
- 对于每个下标 i，我们尝试向左或向右跳跃距离 x（其中 1 <= x <= d）
- 如果可以跳到下标 j，那么 dp[i] = max(dp[i], 1 + dp[j])
由于跳跃方向是从高到低，我们需要确保先计算出较低位置的 dp 值，再计算较高位置的 dp 值。一种方法是使用记忆化搜索（也称为自顶向下的动态规划）。
算法步骤
- 创建一个 dp 数组，dp[i] 表示从下标 i 开始最多可以访问的下标数量
- 将所有 dp[i] 初始化为 1（至少可以访问自身）
- 使用记忆化搜索，对每个下标 i：
- 尝试向左或向右跳跃距离 x（1 <= x <= d）
- 检查跳跃条件：目标位置在数组范围内，且路径上所有点都比起点低
- 如果可以跳到下标 j，则 dp[i] = max(dp[i], 1 + dp[j])
- 返回所有 dp[i] 中的最大值
算法过程
以示例1为例：arr = [6,4,14,6,8,13,9,7,10,6,12], d = 2
让我们跟踪从下标10开始的DFS过程（这是最优起点）：
- 初始化：
- dp[10] = 1（至少可以访问自身）
- 当前下标：10，对应值：12
- 尝试向左跳：
- 检查下标10-1=9：arr[10] > arr[9] (12 > 6) ✓
- 递归计算 dp[9]
- dp[9] = 1（至少可以访问自身）
- 由于没有可跳的地方，dp[9] = 1
- 检查下标10-2=8：arr[10] > arr[8] (12 > 10) ✓
- 递归计算 dp[8]
- dp[8] = 1
- 检查下标8-1=7：arr[8] > arr[7] (10 > 7) ✓
- 递归计算 dp[7]
- dp[7] = 1
- 检查下标7-1=6：arr[7] > arr[6] (7 < 9) ✗ 不能跳
- 检查下标7-2=5：超出范围(d=2)
- 所以 dp[7] = 1
- 更新 dp[8] = 1 + dp[7] = 2
- 检查下标8-2=6：arr[8] > arr[6] (10 > 9) ✓
- 已计算 dp[6] = 1（没有可跳的地方）
- 更新 dp[8] = max(2, 1+1) = 2
- 更新 dp[10] = max(1, 1+dp[8]) = 1+2 = 3
- 检查下标10-1=9：arr[10] > arr[9] (12 > 6) ✓
- 最终路径：
- 下标10 -> 下标8 -> 下标7 -> 可能的终点（无法继续跳跃）
- 或者 下标10 -> 下标8 -> 下标6 -> 可能的终点
- 最多访问4个下标（包括起点10）
事实上，完整的最优路径是：10 -> 8 -> 6 -> 7，总共访问4个下标。
详细代码实现
Java 实现
class Solution {
private int[] dp;
private int[] arr;
private int d;
public int maxJumps(int[] arr, int d) {
int n = arr.length;
this.arr = arr;
this.d = d;
this.dp = new int[n];
// 初始化dp数组，每个位置至少可以访问自身
Arrays.fill(dp, -1);
int maxVisited = 0;
for (int i = 0; i < n; i++) {
maxVisited = Math.max(maxVisited, dfs(i));
}
return maxVisited;
}
private int dfs(int i) {
// 如果已经计算过，直接返回
if (dp[i] != -1) {
return dp[i];
}
// 至少可以访问自身
dp[i] = 1;
// 尝试向右跳
for (int j = i + 1; j <= Math.min(i + d, arr.length - 1); j++) {
// 检查跳跃条件
if (arr[i] <= arr[j]) {
break;
}
// 检查路径上的所有点
boolean canJump = true;
for (int k = i + 1; k < j; k++) {
if (arr[k] >= arr[i]) {
canJump = false;
break;
}
}
if (canJump) {
dp[i] = Math.max(dp[i], 1 + dfs(j));
}
}
// 尝试向左跳
for (int j = i - 1; j >= Math.max(i - d, 0); j--) {
// 检查跳跃条件
if (arr[i] <= arr[j]) {
break;
}
// 检查路径上的所有点
boolean canJump = true;
for (int k = i - 1; k > j; k--) {
if (arr[k] >= arr[i]) {
canJump = false;
break;
}
}
if (canJump) {
dp[i] = Math.max(dp[i], 1 + dfs(j));
}
}
return dp[i];
}
}C# 实现
public class Solution {
private int[] dp;
private int[] arr;
private int d;
public int MaxJumps(int[] arr, int d) {
int n = arr.Length;
this.arr = arr;
this.d = d;
this.dp = new int[n];
// 初始化dp数组
for (int i = 0; i < n; i++) {
dp[i] = -1;
}
int maxVisited = 0;
for (int i = 0; i < n; i++) {
maxVisited = Math.Max(maxVisited, Dfs(i));
}
return maxVisited;
}
private int Dfs(int i) {
// 如果已经计算过，直接返回
if (dp[i] != -1) {
return dp[i];
}
// 至少可以访问自身
dp[i] = 1;
// 尝试向右跳
for (int j = i + 1; j <= Math.Min(i + d, arr.Length - 1); j++) {
// 检查跳跃条件
if (arr[i] <= arr[j]) {
break;
}
// 检查路径上的所有点
bool canJump = true;
for (int k = i + 1; k < j; k++) {
if (arr[k] >= arr[i]) {
canJump = false;
break;
}
}
if (canJump) {
dp[i] = Math.Max(dp[i], 1 + Dfs(j));
}
}
// 尝试向左跳
for (int j = i - 1; j >= Math.Max(i - d, 0); j--) {
// 检查跳跃条件
if (arr[i] <= arr[j]) {
break;
}
// 检查路径上的所有点
bool canJump = true;
for (int k = i - 1; k > j; k--) {
if (arr[k] >= arr[i]) {
canJump = false;
break;
}
}
if (canJump) {
dp[i] = Math.Max(dp[i], 1 + Dfs(j));
}
}
return dp[i];
}
}复杂度分析
- 时间复杂度：O(n²)，其中n是数组的长度。在最坏情况下，对于每个位置，我们需要检查最多2d个可能的跳跃目标，总时间复杂度为O(n * d)。由于d最大可达n，所以最坏情况下时间复杂度是O(n²)。
- 空间复杂度：O(n)，主要用于存储dp数组和递归调用栈。
优化：单调栈方法
上面的实现中，检查路径上的所有点是否都比起点低的时间复杂度是 O(d)，我们可以使用单调栈来优化这一过程，降低时间复杂度。
Java 实现
class Solution {
public int maxJumps(int[] arr, int d) {
int n = arr.length;
int[] dp = new int[n];
Arrays.fill(dp, -1);
// 将下标按照高度排序，从低到高处理
Integer[] indices = new Integer[n];
for (int i = 0; i < n; i++) {
indices[i] = i;
}
Arrays.sort(indices, (a, b) -> arr[a] - arr[b]);
int maxVisited = 0;
for (int idx : indices) {
maxVisited = Math.max(maxVisited, dfs(arr, d, idx, dp));
}
return maxVisited;
}
private int dfs(int[] arr, int d, int i, int[] dp) {
if (dp[i] != -1) {
return dp[i];
}
dp[i] = 1; // 至少可以访问自身
// 向右跳
for (int j = i + 1; j <= Math.min(i + d, arr.length - 1); j++) {
if (arr[i] > arr[j]) {
dp[i] = Math.max(dp[i], 1 + dfs(arr, d, j, dp));
}
// 如果遇到更高或相等的点，则无法继续向右
if (arr[j] >= arr[i]) {
break;
}
}
// 向左跳
for (int j = i - 1; j >= Math.max(i - d, 0); j--) {
if (arr[i] > arr[j]) {
dp[i] = Math.max(dp[i], 1 + dfs(arr, d, j, dp));
}
// 如果遇到更高或相等的点，则无法继续向左
if (arr[j] >= arr[i]) {
break;
}
}
return dp[i];
}
}C#实现
public class Solution {
public int MaxJumps(int[] arr, int d) {
int n = arr.Length;
int[] dp = new int[n];
// 初始化dp数组，所有值设为-1表示未计算
for (int i = 0; i < n; i++) {
dp[i] = -1;
}
// 将下标按照高度排序，从低到高处理
int[] indices = new int[n];
for (int i = 0; i < n; i++) {
indices[i] = i;
}
Array.Sort(indices, (a, b) => arr[a] - arr[b]);
int maxVisited = 0;
foreach (int idx in indices) {
maxVisited = Math.Max(maxVisited, Dfs(arr, d, idx, dp));
}
return maxVisited;
}
private int Dfs(int[] arr, int d, int i, int[] dp) {
// 如果已经计算过，直接返回
if (dp[i] != -1) {
return dp[i];
}
// 至少可以访问自身
dp[i] = 1;
// 向右跳
for (int j = i + 1; j <= Math.Min(i + d, arr.Length - 1); j++) {
if (arr[i] > arr[j]) {
dp[i] = Math.Max(dp[i], 1 + Dfs(arr, d, j, dp));
}
// 如果遇到更高或相等的点，则无法继续向右
if (arr[j] >= arr[i]) {
break;
}
}
// 向左跳
for (int j = i - 1; j >= Math.Max(i - d, 0); j--) {
if (arr[i] > arr[j]) {
dp[i] = Math.Max(dp[i], 1 + Dfs(arr, d, j, dp));
}
// 如果遇到更高或相等的点，则无法继续向左
if (arr[j] >= arr[i]) {
break;
}
}
return dp[i];
}
}复杂度分析
- 时间复杂度：O(n log n + n * d)
- 排序下标需要O(n log n)时间
- 对于每个位置，我们最多检查2d个可能的跳跃目标，总共n个位置，所以是O(n * d)
- 综合起来就是O(n log n + n * d)
- 空间复杂度：O(n)
- 主要用于存储dp数组、排序后的下标数组和递归调用栈
优化与技巧
- 按高度排序处理：先计算高度较低的点的dp值，再计算高度较高的点的dp值，可以减少重复计算。
- 提前终止：如果遇到高度大于等于当前点的位置，可以提前终止搜索，因为无法跳过这个位置。
- 记忆化搜索：使用dp数组存储已计算的结果，避免重复计算。
- 边界检查：确保跳跃不会超出数组范围。
- 利用问题特性：由于只能从高处跳到低处，整个跳跃路径形成了一个有向无环图(DAG)，这使得动态规划可以正确解决此问题。