算法

End of Array Reachable

numbers[i] 表示从 i 位置最多能跳多远,问能否从 0 跳到最后一个下标。

初解

function arrayReachableEnd(numbers: number[]): boolean {
  const n = numbers.length;
  let sum = 0;

  if (numbers[0] === 0) return false;

  for (const num of numbers) {
    sum += num;
  }

  return sum >= n;
}

部分用例无法通过:

[1, 0, 100] [2, 0, 0]

sum 小,不代表跳不到;sum 大,也不代表跳得到。

思路

贪心 只需要维护一个变量 maxReach,表示目前能到达的最远下标。

步骤

  1. 初始化 maxReach = 0
  2. 遍历数组 i,从 0 到最后:
    • 如果 i > maxReach,说明已经无法走到 i,更不可能走到终点,直接返回 false
    • 更新 maxReach = max(maxReach, i + numbers[i])
  3. 如果遍历完成没有中断,则一定能到达终点,返回 true

代码

function canJump(numbers: number[]): boolean {
  let maxReach = 0;

  for (let i = 0; i < numbers.length; i++) {
    if (i > maxReach) return false;
    maxReach = Math.max(maxReach, i + numbers[i]);
  }

  return true;
}
  • 因为 maxReach 始终记录从前面所有可达点能跳到的最远距离
  • 如果某个 i 无法到达,则 i 之后的位置更不可能到达
  • 只要你遍历到最后一个 index,就说明中间没有断层

时间复杂度:O(n)O(n) 空间复杂度:O(1)O(1)

在 GitHub 上编辑

上次更新于