如何修正最小跳跃次数II的O(n)贪心算法以通过测试用例？

问题背景 #

给定包含N个整数的数组arr[]，每个元素代表从该位置可向前跳跃的最大长度，求从第一个元素出发到达数组末尾的最少跳跃次数；若元素为0则无法从此处移动，无法到达末尾时返回-1。

原算法的缺陷 #

参考的贪心算法通过跟踪当前范围内的maxReach求解，但存在逻辑错误：当当前范围结束需要进入下一个范围时，若当前位置为0，直接返回-1，忽略了之前已记录的maxReach可能覆盖到更远位置的情况。比如测试用例N=15，arr=[9,10,1,2,3,4,8,0,0,0,0,0,0,0,1]，原算法会在i=9时错误返回-1，但实际可通过索引6的元素8跳跃到末尾。

原算法代码 #

static int minJumps(int[] arr){
    int n = arr.length; 
    if(n <= 1) return 0;   
    int maxReach = arr[0];
    int stepsCount = arr[0];
    int jumps = 0;
    int start = 1;
    while(start < n-1){
        maxReach = Math.max(maxReach, start+arr[start]);
        stepsCount--;
        if(stepsCount == 0){
            if(arr[start] == 0) return -1;
            jumps++;
            stepsCount = maxReach-start;
        }
        start++;
    }
    if(jumps == 0 && stepsCount > 0) return 1;  
    return jumps==0?-1:jumps+1;         
}

错误的修改尝试 #

尝试增加start变量回溯，但破坏了O(n)时间复杂度，出现超时，且正确性存疑：

static int minJumps(int[] arr){       
    int n = arr.length;
    if(n <= 1) return 0;
    int maxReach = arr[0];
    int stepsCount = arr[0];
    int jumps = 0;
    int start = 0;
    int i = 1;
    while(i < n-1){
        if(arr[i] != 0) maxReach = Math.max(maxReach, i+arr[i]);
        stepsCount--;
        if(stepsCount == 0){
            // this block checks if we have prev option then try those
            if(arr[i] == 0){
                if(start == i) return -1;
                i = start+2;
                stepsCount = arr[start+1];
                maxReach = arr[start+1];
                continue;
            }
            jumps++;
            start = i;
            stepsCount = maxReach-i;
        }
        i++;
    }
    if(stepsCount > 0 || jumps != 0) return jumps+1;  
    return -1;
}

正确的O(n)贪心算法修正 #

核心错误在于原算法判断无法前进的条件：不应检查当前位置是否为0，而是要判断当前的maxReach是否无法覆盖到下一个位置。只要maxReach大于等于当前索引，就说明还能继续探索更远的位置。

修正后的代码 #

static int minJumps(int[] arr) {
    int n = arr.length;
    if (n <= 1) return 0;
    // 无法从起点出发的情况
    if (arr[0] == 0) return -1;

    int maxReach = arr[0];
    int steps = arr[0];
    int jumps = 1;

    for (int i = 1; i < n; i++) {
        // 到达终点
        if (i == n - 1) return jumps;

        // 更新能到达的最远距离
        maxReach = Math.max(maxReach, i + arr[i]);
        steps--;

        // 当前可用步数耗尽，需要跳一次
        if (steps == 0) {
            jumps++;
            // 判断是否还能前进：如果当前位置超过了maxReach，说明无法继续
            if (i >= maxReach) return -1;
            // 更新剩余步数为当前maxReach到当前位置的距离
            steps = maxReach - i;
        }
    }
    return -1;
}

修正逻辑说明 #

1. 初始判断：先处理数组长度为1的情况，以及起点为0无法出发的情况。
2. 遍历过程：
   • 每一步都更新maxReach，记录当前能到达的最远位置。
   • 当steps（当前范围内剩余可用步数）耗尽时，必须进行一次跳跃：
     • 此时检查当前索引i是否超过maxReach，如果超过，说明后续位置都无法到达，返回-1。
     • 否则，将steps更新为maxReach - i，即新范围内的可用步数。
3. 终点判断：当遍历到数组最后一个元素时，直接返回当前的跳跃次数。

这个修正后的算法保持了O(n)的时间复杂度，每个元素只遍历一次，同时正确处理了原算法中的测试用例：在遍历到索引9时，maxReach已经被索引6的元素更新为6+8=14（即数组末尾），因此当steps耗尽时，i=9小于maxReach=14，会继续更新steps并完成后续遍历，最终到达终点返回正确的跳跃次数。

内容的提问来源于stack exchange，提问作者Ravi Khinchi