如何找到在 O（n） 时间内到达数组末尾的最小跳转次数

站点上提出的解决方案的时间复杂度是线性的，因为您只需迭代数组一次。该算法通过使用一些聪明的技巧来避免我提出的解决方案的内部迭代。

该变量始终存储数组中的最大可到达位置。 存储到达该位置所需的跳跃量。 存储我们仍然可以执行的步骤量（并使用第一个数组位置的步数初始化）maxReachjumpstep

在迭代过程中，上述值将按如下方式更新：

首先，我们测试我们是否已经到达数组的末尾，在这种情况下，我们只需要返回变量。jump

接下来，我们更新最大可到达位置。这等于 和 的最大值（我们可以从当前位置采取的步数）。maxReachi+A[i]

我们用了一个步骤来获得当前指数，所以必须减少。steps

如果没有更多的步骤（即 ，那么我们必须使用跳转。因此增加.由于我们知道有可能以某种方式达到 ，我们将步骤初始化为从位置到达的步骤量。steps=0jumpmaxReachmaxReachi

public class Solution {
    public int jump(int[] A) {
        if (A.length <= 1)
            return 0;
        int maxReach = A[0];
        int step = A[0];
        int jump = 1;
        for (int i = 1; i < A.length; i++) {
           if (i == A.length - 1)
                return jump;
            if (i + A[i] > maxReach)
                maxReach = i + A[i];
            step--;
            if (step == 0) {
                jump++;
                step = maxReach - i;
            } 
        }
        return jump;
    }
}

例：

int A[] = {1, 3, 5, 8, 9, 2, 6, 7, 6, 8, 9}
int maxReach = A[0];     // A[0]=1, so the maximum index we can reach at the moment is 1.
int step = A[0];         // A[0] = 1, the amount of steps we can still take is also 1.
int jump = 1;            // we will always need to take at least one jump.

/*************************************
 * First iteration (i=1)
 ************************************/
if (i + A[i] > maxReach) // 1+3 > 1, we can reach further now!
    maxReach = i + A[i]  // maxReach = 4, we now know that index 4 is the largest index we can reach.

step--                   // we used a step to get to this index position, so we decrease it
if (step == 0) {
    ++jump;              // we ran out of steps, this means that we have made a jump
                         // this is indeed the case, we ran out of the 1 step we started from. jump is now equal to 2.
                         // but we can continue with the 3 steps received at array position 2.
    steps = maxReach-i   // we know that by some combination of 2 jumps, we can reach  position 4.
                         // therefore in the current situation, we can minimaly take 3
                         // more steps to reach position 4 => step = 3
}

/*************************************
 * Second iteration (i=2)
 ************************************/
if (i + A[i] > maxReach) // 2+5 > 4, we can reach further now!
    maxReach = i + A[i]  // maxReach = 7, we now know that index 7 is the largest index we can reach.

step--                   // we used a step so now step = 2
if (step==0){
   // step 
}

/*************************************
 * Second iteration (i=3)
 ************************************/
if (i + A[i] > maxReach) // 3+8 > 7, we can reach further now!
    maxReach = i + A[i]  // maxReach = 11, we now know that index 11 is the largest index we can reach.

step--                   // we used a step so now step = 1
if (step==0){
   // step 
}

/*************************************
 * Third iteration (i=4)
 ************************************/
if (i + A[i] > maxReach) // 4+9 > 11, we can reach further now!
    maxReach = i + A[i]  // maxReach = 13, we now know that index 13 is the largest index we can reach.

step--                   // we used a step so now step = 0
if (step == 0) {
    ++jump;              // we ran out of steps, this means that we have made a jump.
                         // jump is now equal to 3.
    steps = maxReach-i   // there exists a combination of jumps to reach index 13, so
                         // we still have a budget of 9 steps
}


/************************************
 * remaining iterations
 ***********************************
// nothing much changes now until we reach the end of the array.

我的次优算法，它及时处理数组中的元素数量和数组中最大的元素，并使用内部循环。以下算法可避免此循环。O(nk)nkarray[i]

法典

public static int minimum_steps(int[] array) {
    int[] min_to_end = new int[array.length];
    for (int i = array.length - 2; i >= 0; --i) {
        if (array[i] <= 0)
            min_to_end[i] = Integer.MAX_VALUE;
        else {
            int minimum = Integer.MAX_VALUE;
            for (int k = 1; k <= array[i]; ++k) {
                if (i + k < array.length)
                    minimum = Math.min(min_to_end[i+k], minimum);
                else
                    break;
            }
            min_to_end[i] = minimum + 1;
        }
    }
    return min_to_end[0];
} 

这是关于上述问题的贪婪方法的基本直觉，其余的都是代码要求。

给定数组为输入：a[] = {1， 3， 5， 8， 9， 2， 6， 7， 6， 8， 9}。

现在我们从第一个元素开始，即 i=0 和 a[i] = 1。因此，看到这一点，我们最多可以进行1次跳跃，因此由于我们没有任何其他选择，因此我们实现这一步。

目前我们处于 i=1 和 a[i]=3。因此，我们目前可以进行大小为3的跳跃，但是相反，我们考虑从当前位置可以进行的所有可能的跳跃，并达到数组范围内的最大距离。那么我们的选择是什么呢？我们可以跳跃1步，或2步或3步。因此，我们从当前位置调查每个大小的跳跃，并选择可以最大限度地将我们带入数组的跳跃。

一旦我们决定了，我们坚持哪一个，我们采取跳跃大小，并更新我们到目前为止所做的跳跃次数，以及我们最多可以达到的位置以及我们现在有多少步数来决定我们的下一步。就是这样。这就是我们最终选择线性遍历数组的最佳选项的方式。因此，这是您可能正在寻找的算法的基本思想，接下来是对其进行编码以使算法正常工作。干杯！

希望有人时间旅行，发现直觉有帮助！:) :P安德烈@Vasilescu“派对迟到多年”-说得好。有时我觉得我们是时间旅行者。