讨论/《零起步学算法》 - 跳跃游戏 II/
《零起步学算法》 - 跳跃游戏 II
共 3 个回复

威哥,这个贪心的代码看不懂啊,能再详细解释一下吗?

1

哦,我明白了,相当于在整个数组遍历过程中,以currMaxReached为一组来个”小的for循环遍历“,求出这次”小的for循环遍历“所达到的最远的位置nextMaxReached,然后立马赋值给currMaxReached,以便再进行下一次”小的for遍历",再次求出最大值,依次类推...是这样吧?威哥

currMaxReached 可以认为是当前执行一次跳跃能够跳到的最远的地方,我们记录在区间 [i..currMaxReached] 里可以到达的最远的位置为 nextMaxReached

因此当 i 遍历到 currMaxReached 的时候,表示不得不再执行一次跳跃(res++),才可以跳到更远的地方,可以再看看上面「贪心算法」的直觉里的叙述。此时需要更新 currMaxReachednextMaxReached

  • currMaxReached 就等于 nextMaxReached
  • nextMaxReached 在遍历的时候记录下来

不知道我解释清楚没有,有问题可以再交流哈。