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

Question

问题 给定一个整数数组，其中每个元素表示可以从该元素前进的最大步骤数。编写一个函数，返回到达数组末尾的最小跳转次数(从第一个元素开始)。如果元素为0，则不能在该元素中移动。 示例 输入: arr[] = {1，3，5，8，9，2，6，7，6，8，9} 输出:3 (1-> 3 -> 8 ->9)

找到了从动态规划法到其他线性方法的多种方法。我无法理解所谓的时间线性的方法。这里是提出线性方法的环节。

我一点也听不懂。我能理解的是，作者建议采取一种贪婪的态度，看看我们是否达到了目的。如果没有，那就回头路？

Answer 1

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

变量maxReach在任何时候都存储数组中的最大可达位置。jump存储到达该位置所需的跳转量。step存储我们仍然可以采取的步骤的数量(并且在第一个数组位置用步骤的数量进行初始化)

在迭代期间，对上述值进行如下更新：

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

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

为了达到当前的索引，我们花费了一步时间，因此必须减少steps。

如果没有剩下的步骤(即steps=0，那么我们必须使用跳转。因此，增加jump。由于我们知道以某种方式到达maxReach是可能的，所以我们将这些步骤初始化为从i位置到达maxReach的步骤数。

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)时间与n、数组中的元素数和数组中最大的元素k一起工作，并在array[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];
} 

Answer 2

下面是关于上述问题的基本直觉，贪婪的方法和rest是代码需求。

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

现在我们从第一个元素，即i=0和ai = 1开始，看到这一点，我们最多可以跳1，所以由于我们没有其他选择，所以我们实现了这个步骤。

目前我们在i=1和ai=3，所以我们现在可以跳到3级，但是我们考虑了所有可能的跳转，我们可以从当前的位置跳到最大的距离(在数组的范围内)。那我们有什么选择呢？我们可以跳1步，或2步或3步。因此，我们从当前位置研究每个大小跳跃，并选择一个可以使我们进一步深入到数组中的。

一旦我们决定了，我们坚持哪一个，我们采取了跳跃的大小，更新了我们的跳跃次数，我们最多可以到达哪里，以及我们现在要采取多少步骤来决定下一步。就是这样。这就是最后我们如何选择线性遍历数组的最佳选项。这就是你可能要寻找的algo的基本思想，接下来是为算法工作编写代码。干杯!

希望有人时间旅行，发现直觉有帮助!！) :P：“迟到几年”@Vasilescu Andrei - well说。有时我觉得我们是时间旅行者。

Answer 3

到目前为止，这里的许多答案都是很棒的，但是我觉得我可以帮助解释为什么算法是正确的以及它背后的直觉。

我喜欢这个问题，因为它是一个直观的动态编程方法在O(n^2)最坏情况下运行的问题，而贪婪方法(激发这个问题的方法)在O(n)最坏的情况下运行(实际上它只访问数组的每个元素一次)。对于我来说，这个算法有点让人想起Dijkstra的算法，它解决了另一个单一来源的最短路径问题，这也是贪婪的。

首先，请记住问题语句，A[i]保持从该索引跳到的最大位置，但是可以从i获取一个短跳，如果A[i]>1，那么从i=0跳到的最短序列可以是较短跳E 215，而不是每个索引所允许的。这一点很重要，因为您将看到算法从不显式地考虑那些较小的跳转或它们的位置。

其次，它有助于将您提到的算法想象成一种让自己“一股绳子”(steps = maxReach - i;)到达终点的算法，并且它在试图通过数组前进时消耗了这条绳子(steps--;)。

第三，注意算法是而不是，它跟踪可能是a 最短序列一部分的特定索引i，从输入数组A的开始到结束。实际上，该算法只在“用完了绳子”(来自前一股)时增加变量jump (它给自己一条新的绳子)，这样它就可以在主循环中继续迭代以“尝试”到达终点。

更具体地说，要使算法正确，需要：

1. 当在数组中向前移动时，它会跟踪“它能到达多远”(maxReach)的位置-- i。请注意，每个位置都更新了这个数量，即使在当时已经很清楚，到达新位置需要采取更多的“跳转”，因为您已经超过了之前给自己的步骤数(即用完了绳子)，如果没有最短路径将实际访问该元素，甚至。这些更新的目标是确定下一次跳转能达到多远，这样一旦耗尽了当前的跳绳，它就可以给自己提供更多的绳子。
2. 如果要继续遍历数组以到达末尾，则必须使用Account来表示跳转的最小次数 (jumps)，因为从前一条线上用完了绳子(steps)。

链接到的算法，以供参考：

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;
    }
}