从数组的第 0 个位置开始跳，跳的距离小于等于数组上对应的数。求出跳到最后个位置需要的最短步数。比如上图中的第 0 个位置是 2，那么可以跳 1 个距离，或者 2 个距离，我们选择跳 1 个距离，就跳到了第 1 个位置，也就是 3 上。然后我们可以跳 1，2，3 个距离，我们选择跳 3 个距离，就直接到最后了。所以总共需要 2 步。

解法一 顺藤摸瓜

参考这里，leetCode 讨论里，大部分都是这个思路，贪婪算法，我们每次在可跳范围内选择可以使得跳的更远的位置。

如下图，开始的位置是 2，可跳的范围是橙色的。然后因为 3 可以跳的更远，所以跳到 3 的位置。

写代码的话，我们用 end 表示当前能跳的边界，对于上边第一个图的橙色 1，第二个图中就是橙色的 4，遍历数组的时候，到了边界，我们就重新更新新的边界。

publicintjump(int[] nums) {
intend=0;
intmaxPosition=0; 
intsteps=0;
for(inti=0; i<nums.length-1; i++){
//找能跳的最远的maxPosition=Math.max(maxPosition, nums[i] +i); 
if( i==end){ //遇到边界，就更新边界，并且步数加一end=maxPosition;
steps++;
        }
    }
returnsteps;
}

时间复杂度：O（n）。

空间复杂度：O（1）。

这里要注意一个细节，就是 for 循环中，i < nums.length - 1，少了末尾。因为开始的时候边界是第 0 个位置，steps 已经加 1 了。如下图，如果最后一步刚好跳到了末尾，此时 steps 其实不用加 1 了。如果是 i < nums.length，i 遍历到最后的时候，会进入 if 语句中，steps 会多加 1 。

总

刷这么多题，第一次遇到了贪心算法，每次找局部最优，最后达到全局最优，完美！