Question

1340. Jump Game V

中文文档

Description

Given an array of integers arr and an integer d. In one step you can jump from index i to index:

• i + x where: i + x < arr.length and 0 < x <= d.
• i - x where: i - x >= 0 and 0 < x <= d.

In addition, you can only jump from index i to index j if arr[i] > arr[j] and arr[i] > arr[k] for all indices k between i and j (More formally min(i, j) < k < max(i, j)).

You can choose any index of the array and start jumping. Return _the maximum number of indices_ you can visit.

Notice that you can not jump outside of the array at any time.

 

Example 1:

Input: arr = [6,4,14,6,8,13,9,7,10,6,12], d = 2
Output: 4
Explanation: You can start at index 10. You can jump 10 --> 8 --> 6 --> 7 as shown.
Note that if you start at index 6 you can only jump to index 7. You cannot jump to index 5 because 13 > 9. You cannot jump to index 4 because index 5 is between index 4 and 6 and 13 > 9.
Similarly You cannot jump from index 3 to index 2 or index 1.

Example 2:

Input: arr = [3,3,3,3,3], d = 3
Output: 1
Explanation: You can start at any index. You always cannot jump to any index.

Example 3:

Input: arr = [7,6,5,4,3,2,1], d = 1
Output: 7
Explanation: Start at index 0. You can visit all the indicies. 

 

Constraints:

• 1 <= arr.length <= 1000
• 1 <= arr[i] <= 105
• 1 <= d <= arr.length

Solutions

Solution 1

class Solution:
  def maxJumps(self, arr: List[int], d: int) -> int:
    @cache
    def dfs(i):
      ans = 1
      for j in range(i - 1, -1, -1):
        if i - j > d or arr[j] >= arr[i]:
          break
        ans = max(ans, 1 + dfs(j))
      for j in range(i + 1, n):
        if j - i > d or arr[j] >= arr[i]:
          break
        ans = max(ans, 1 + dfs(j))
      return ans

    n = len(arr)
    return max(dfs(i) for i in range(n))

class Solution {
  private int n;
  private int d;
  private int[] arr;
  private Integer[] f;

  public int maxJumps(int[] arr, int d) {
    n = arr.length;
    this.d = d;
    this.arr = arr;
    f = new Integer[n];
    int ans = 1;
    for (int i = 0; i < n; ++i) {
      ans = Math.max(ans, dfs(i));
    }
    return ans;
  }

  private int dfs(int i) {
    if (f[i] != null) {
      return f[i];
    }
    int ans = 1;
    for (int j = i - 1; j >= 0; --j) {
      if (i - j > d || arr[j] >= arr[i]) {
        break;
      }
      ans = Math.max(ans, 1 + dfs(j));
    }
    for (int j = i + 1; j < n; ++j) {
      if (j - i > d || arr[j] >= arr[i]) {
        break;
      }
      ans = Math.max(ans, 1 + dfs(j));
    }
    return f[i] = ans;
  }
}

class Solution {
public:
  int maxJumps(vector<int>& arr, int d) {
    int n = arr.size();
    int f[n];
    memset(f, 0, sizeof(f));
    function<int(int)> dfs = [&](int i) -> int {
      if (f[i]) {
        return f[i];
      }
      int ans = 1;
      for (int j = i - 1; j >= 0; --j) {
        if (i - j > d || arr[j] >= arr[i]) {
          break;
        }
        ans = max(ans, 1 + dfs(j));
      }
      for (int j = i + 1; j < n; ++j) {
        if (j - i > d || arr[j] >= arr[i]) {
          break;
        }
        ans = max(ans, 1 + dfs(j));
      }
      return f[i] = ans;
    };
    int ans = 1;
    for (int i = 0; i < n; ++i) {
      ans = max(ans, dfs(i));
    }
    return ans;
  }
};

func maxJumps(arr []int, d int) (ans int) {
  n := len(arr)
  f := make([]int, n)
  var dfs func(int) int
  dfs = func(i int) int {
    if f[i] != 0 {
      return f[i]
    }
    ans := 1
    for j := i - 1; j >= 0; j-- {
      if i-j > d || arr[j] >= arr[i] {
        break
      }
      ans = max(ans, 1+dfs(j))
    }
    for j := i + 1; j < n; j++ {
      if j-i > d || arr[j] >= arr[i] {
        break
      }
      ans = max(ans, 1+dfs(j))
    }
    f[i] = ans
    return ans
  }
  for i := 0; i < n; i++ {
    ans = max(ans, dfs(i))
  }
  return
}

Solution 2

class Solution:
  def maxJumps(self, arr: List[int], d: int) -> int:
    n = len(arr)
    f = [1] * n
    for x, i in sorted(zip(arr, range(n))):
      for j in range(i - 1, -1, -1):
        if i - j > d or arr[j] >= x:
          break
        f[i] = max(f[i], 1 + f[j])
      for j in range(i + 1, n):
        if j - i > d or arr[j] >= x:
          break
        f[i] = max(f[i], 1 + f[j])
    return max(f)

class Solution {
  public int maxJumps(int[] arr, int d) {
    int n = arr.length;
    Integer[] idx = new Integer[n];
    for (int i = 0; i < n; ++i) {
      idx[i] = i;
    }
    Arrays.sort(idx, (i, j) -> arr[i] - arr[j]);
    int[] f = new int[n];
    Arrays.fill(f, 1);
    int ans = 0;
    for (int i : idx) {
      for (int j = i - 1; j >= 0; --j) {
        if (i - j > d || arr[j] >= arr[i]) {
          break;
        }
        f[i] = Math.max(f[i], 1 + f[j]);
      }
      for (int j = i + 1; j < n; ++j) {
        if (j - i > d || arr[j] >= arr[i]) {
          break;
        }
        f[i] = Math.max(f[i], 1 + f[j]);
      }
      ans = Math.max(ans, f[i]);
    }
    return ans;
  }
}

class Solution {
public:
  int maxJumps(vector<int>& arr, int d) {
    int n = arr.size();
    vector<int> idx(n);
    iota(idx.begin(), idx.end(), 0);
    sort(idx.begin(), idx.end(), [&](int i, int j) { return arr[i] < arr[j]; });
    vector<int> f(n, 1);
    for (int i : idx) {
      for (int j = i - 1; j >= 0; --j) {
        if (i - j > d || arr[j] >= arr[i]) {
          break;
        }
        f[i] = max(f[i], 1 + f[j]);
      }
      for (int j = i + 1; j < n; ++j) {
        if (j - i > d || arr[j] >= arr[i]) {
          break;
        }
        f[i] = max(f[i], 1 + f[j]);
      }
    }
    return *max_element(f.begin(), f.end());
  }
};

func maxJumps(arr []int, d int) int {
  n := len(arr)
  idx := make([]int, n)
  f := make([]int, n)
  for i := range f {
    idx[i] = i
    f[i] = 1
  }
  sort.Slice(idx, func(i, j int) bool { return arr[idx[i]] < arr[idx[j]] })
  for _, i := range idx {
    for j := i - 1; j >= 0; j-- {
      if i-j > d || arr[j] >= arr[i] {
        break
      }
      f[i] = max(f[i], 1+f[j])
    }
    for j := i + 1; j < n; j++ {
      if j-i > d || arr[j] >= arr[i] {
        break
      }
      f[i] = max(f[i], 1+f[j])
    }
  }
  return slices.Max(f)
}