LC45. 跳跃游戏II

题目描述

给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。 每个元素 nums[i] 表示从索引 i 向前跳转的最大长度。换句话说，如果你在 nums[i] 处，你可以跳转到任意 nums[i + j] 处: 0 <= j <= nums[i] i + j < n 返回到达 nums[n - 1] 的最小跳跃次数。生成的测试用例可以到达 nums[n - 1]。 示例 1: 输入: nums = [2,3,1,1,4] 输出: 2 解释: 跳到最后一个位置的最小跳跃数是 2。 从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。 示例 2: 输入: nums = [2,3,0,1,4] 输出: 2 提示: 1 <= nums.length <= 10^4 0 <= nums[i] <= 1000

题目解析

题目在说什么

想象你站在一条直线上的起点，每个格子上写着一个数字，比如 [2,3,1,1,4]。数字表示从这格起跳，你最多能往前跳几步（但也可以跳更少步数）。你的目标是跳到最后一个格子（位置4），并且希望跳跃次数尽可能少。题目保证一定能跳到终点。

比如例子中：从位置0（数字2）可以跳到位置1或2，如果跳到位置1（数字3），再跳一次就能到终点（因为从位置1最多跳3步，直接到位置4）。总共跳了2次，这就是最少次数。

思路是怎么来的

这个问题很像“跳格子游戏”，但难点在于：你不知道下一步该跳到哪个格子，才能让总跳跃次数最少。

一个直观的想法是：每次跳的时候，不要只看眼前，要选一个“能让你下一步跳得更远”的格子。就像你玩跳棋，如果当前格子能跳到好几个格子，你会选那个能让你下一步覆盖范围最大的格子。因为这样你就有更多选择，更可能尽快到达终点。

这就是“贪心”思想：每次做局部最优选择（选能跳最远的下一格），最终得到全局最优（最少跳跃次数）。

具体做法是： 1. 站在当前格子，先看看它最远能跳到哪（右边界）。 2. 如果这个右边界已经包含终点，那直接跳过去就行。 3. 否则，在“当前格子能跳到的所有格子”中，找一个格子，这个格子本身能跳到的位置最远（即它的位置加上它的数字最大）。然后跳到这个格子。 4. 重复以上步骤，直到到达终点。

代码逐步拆解

我们对照参考代码，一步步看它是怎么实现的。

int nowPos = 0;      // 当前所在位置（索引）
int step = 0;        // 已经跳了多少次

第1步：循环条件

while( nowPos < nums.length - 1){

只要还没到终点（最后一个位置），就继续跳。因为题目保证能到，所以循环一定会结束。

第2步：计算当前能跳的最远位置

int right = nowPos + nums[nowPos];

right 是从当前位置 nowPos 跳一次能到达的最远索引。比如 nowPos=0，nums[0]=2，则 right=0+2=2，表示能跳到位置1或2。

第3步：检查是否能直接到终点

if( right >= nums.length - 1) return step + 1;

如果 right 已经大于等于最后一个位置（nums.length-1），说明当前这一跳就能到终点，直接返回 step+1（因为还要再跳一次）。这是最快的情况。

第4步：在可跳范围内找最佳下一跳

int nextRight = right;   // 记录下一个跳跃点的最远可达位置，初始化为当前最远
int nextPos = nowPos;    // 记录下一个跳跃点的位置，初始化为当前

for ( int i = nowPos + 1 ; i <= right ; i++){
    if( i + nums[i] > nextRight){
        nextRight = i + nums[i];
        nextPos = i;
    }
}

这个循环在 [nowPos+1, right] 区间内（即当前能跳到的所有格子）寻找一个格子 i，使得 i + nums[i] 最大。i + nums[i] 表示从格子 i 起跳能到达的最远位置。我们选那个能让下一步跳得最远的格子作为下一跳位置。