问题描述

给定一个非负整数数组 nums，你最初位于数组的第一个下标。数组中的每个元素代表你在该位置可以跳跃的最大长度。你的目标是使用最少的跳跃次数到达数组的最后一个下标。假设对于所有测试用例，你总能到达最后一个下标。

示例 1:

<strong>输入:</strong> nums = [2,3,1,1,4]
<strong>输出:</strong> 2
<strong>解释:</strong> 跳到最后一个位置的最小跳跃数是 2。
     从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。

示例 2:

<strong>输入:</strong> nums = [2,3,0,1,4]
<strong>输出:</strong> 2

算法解析

本题的核心在于如何以最优的方式选择落脚点。由于我们追求的是"最少跳跃次数"，这天然契合贪心算法（Greedy Algorithm）的思想。在遍历数组时，我们不需要真正决定每一步具体跳到哪个下标，而是关注"当前这一步能覆盖的最远范围"以及"在下一步能达到的最远范围"。

我们可以维护三个关键状态：

• jumps：记录已经进行的跳跃次数。
• currentEnd：当前跳跃步数所能到达的最远边界。
• maxReach：在当前边界内，通过再跳跃一次所能到达的全局最远位置。

当我们从左到右遍历数组时，不断更新 maxReach。一旦遍历的下标 i 达到了 currentEnd，说明当前这一步的潜力已经耗尽，必须进行一次新的跳跃（jumps 加 1），并将 currentEnd 更新为之前计算出的 maxReach。为了避免在数组末尾进行不必要的跳跃判断，我们的遍历范围只需到 nums.length - 2 即可，因为只要能够覆盖或越过最后一个元素，任务就完成了。

代码实现

class Solution {
    public int jump(int[] nums) {
        int n = nums.length;
        // 如果数组只有一个元素，不需要跳跃
        if (n <= 1) {
            return 0;
        }
        
        int jumps = 0;
        int currentEnd = 0;
        int maxReach = 0;
        
        // 只需要遍历到倒数第二个元素，因为到达最后一个元素即算成功
        for (int i = 0; i < n - 1; i++) {
            // 更新从当前位置能跳到的最远位置
            maxReach = Math.max(maxReach, i + nums[i]);
            
            // 如果到达了当前跳跃的边界
            if (i == currentEnd) {
                jumps++;
                currentEnd = maxReach;
                
                // 提前终止条件：如果当前边界已经能覆盖或超过终点
                if (currentEnd >= n - 1) {
                    break;
                }
            }
        }
        
        return jumps;
    }
}