最小跳跃次数：O(N) 贪心算法详解

本文深入探讨了如何使用O(N)时间复杂度的贪心算法解决“最小跳跃次数”问题。我们将详细分析一个常见的贪心策略，指出其潜在的缺陷，并提供一个经过修正的、鲁棒的解决方案。核心思想是在每次跳跃中最大化可达范围，并在步数耗尽时进行关键的有效性检查，以确保能够继续前进。

1. 问题概述

“最小跳跃次数”问题要求我们找到从数组的第一个元素（索引0）跳到数组最后一个元素（索引 n-1）所需的最小跳跃次数。数组中的每个元素 arr[i] 代表从当前位置 i 可以向前跳跃的最大长度。如果 arr[i] 为0，则表示无法从该位置跳跃。如果无法到达数组末尾，则返回 -1。

例如：

• arr = [2, 3, 1, 1, 4]，最小跳跃次数为 2。
  • 从索引 0 (值为 2) 跳到索引 1 (值为 3)。
  • 从索引 1 (值为 3) 跳到索引 4 (数组末尾)。
• arr = [1, 0, 0, 3]，最小跳跃次数为 -1。
  • 从索引 0 (值为 1) 只能跳到索引 1。
  • 从索引 1 (值为 0) 无法跳跃，无法到达末尾。

2. 贪心策略的核心思想

解决此类问题通常采用贪心算法。其核心思想是：在当前可达的范围内，总是选择能跳得最远的那一步，以最小化跳跃次数。

我们维护以下三个关键变量：

• maxReach: 从当前跳跃的起始点开始，能够到达的最远索引。在遍历过程中，我们会不断更新这个值，确保它总是当前已知能达到的最远位置。
• steps: 当前跳跃剩余的步数。每向前移动一个位置，就消耗一步。
• jumps: 已经完成的跳跃次数。

算法流程（初步设想）：

1. 初始化 jumps = 1 (因为从索引0开始就是一次跳跃的开始)，maxReach = arr[0]，steps = arr[0]。
2. 从索引 i = 1 开始遍历数组，直到 n-1。
3. 在每一步 i：
   • 更新 maxReach = Math.max(maxReach, i + arr[i])。这意味着从当前位置 i 跳跃，可以到达的最远位置。
   • steps–，消耗一步。
   • 如果 steps == 0，表示当前跳跃的步数已用尽，需要进行下一次跳跃：
     • jumps++，增加跳跃次数。
     • 关键判断： 此时需要检查是否能够继续前进。如果 maxReach 并没有比当前位置 i 更远（即 maxReach
     • 否则，更新 steps = maxReach – i。这表示从当前位置 i 到 maxReach 还需要多少步，这些步数将构成下一次跳跃的“燃料”。
4. 如果在遍历过程中 i 达到了 n-1，则表示成功到达终点，返回 jumps。

3. 常见陷阱与修正

许多初学者在实现上述贪心策略时，会遇到一个常见问题，尤其是在遇到值为0的元素时。

错误示例（简化版的问题代码逻辑）：

// 伪代码，模拟问题中提到的错误逻辑 if (stepsCount == 0) {     if (arr[start] == 0) return -1; // 错误判断：只检查当前元素是否为0     jumps++;     stepsCount = maxReach - start; }

这个错误在于，当 stepsCount 变为0时，如果 arr[start] (即 arr[i]) 为0，代码会立即返回 -1。然而，这忽略了 maxReach 的作用。maxReach 记录的是从当前跳跃的起始点，通过之前遇到的任何元素能跳到的最远位置。即使当前元素 arr[i] 是0，但如果之前有某个元素 arr[k] (其中 k

示例分析：arr[] = 9 10 1 2 3 4 8 0 0 0 0 0 0 0 1 (N=15)

在这个例子中，当 i 遍历到索引 9 时，arr[9] 的值为 0。如果按照上述错误逻辑，在 stepsCount 变为 0 时，会检查 arr[9] 是否为 0，然后直接返回 -1。但这实际上是错误的。因为在 i=6 时，arr[6]=8，这使得 maxReach 更新为 6+8=14。当 i=9 时 stepsCount 变为 0，虽然 arr[9]=0，但 maxReach