leetcode 第45题：跳跃游戏2
学好算法没有捷径，最好的捷径就是多刷题，并且跳出舒适区，每道题都要寻找最优解，也不能老是做那些你自己比较擅长的题，不定期更新 Leetcode 的题，每道题都会给出多种解法以及最优解。
题目描述
给定一个非负整数数组，你最初位于数组的第一个位置。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
你的目标是使用最少的跳跃次数到达数组的最后一个位置。
示例:
输入: [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2。
从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。
说明：假设你总是可以到达数组的最后一个位置。
方法一、从右往左搜索
我们的目的是要跳跃到最后一个点上，我们可以从最后一个点往左开始寻找，例如非负数组为 arr = {2,3,1,1,4,2,1}，从最右边的 1 往左寻找，找那个离右边的点最远，却又能到达它的点，如下图：
寻找每一个点的过程中，我们每次都需要遍历一遍数组，看看哪一个点更加合适，所以需要两层循环，时间复杂度为 O(n^2)，空间复杂度为 O(1)。代码如下
public int jump(int[] nums){
int right = nums.length - 1;
int sum = 0;
while(right > 0){
// 寻找离 last 最远，且能够到达 last 的点
int cur = right - 1;
for(int i = right - 2; i >= 0; i--){
// 是否能够达到 last 这个点
if( i + nums[i] >= right){
cur = i;
}
}
right = cur;
sum++;
}
return sum;
}
方法二：贪心算法
这道题的最优解是可以时间复杂度优化到 O(n) 的，那就是采用贪心算法，我们从左边的起点开始跳跃的时候，我们应该跳跃到哪一个点比较合适呢？，显然，每次都跳跃最大长度的话，是不行的。例如对于上面 arr = {2, 3, 1, 1, 4, 2, 1} 这个例子，刚开 arr[0] = 2，那么我们可以跳到 arr[1] = 3 或者 arr[2] = 1 上，显然，我们跳跃 arr[1] = 3 会更好一点。如图（图片来源于网络）
接着同样的道理，我们可以从 arr[1] = 3 这个位置开始跳跃，它可以跳跃到 arr[2] = 1, arr[3] = 1, arr[4] = 4 这三个位置，显然，我们跳到 arr[4] = 4 这个位置好一点，如图（图片来源于网络）
也就是说，我们要跳跃的那个点，可以使得上一次 + 下一次的跳跃总距离最远。代码如下
public int jump(int[] nums) {
if(nums.length < 2)
return 0;
int sum = 0;
int end = 0; // 能跳到的最远距离
int max = 0; // 下一步可以跳到的最远距离
for(int i = 0; i < nums.length - 1; i++){
max = Math.max(max, i + nums[i]);
// 更新当前点
if(i == end){
end = max;
sum++;
}
}
return sum;
}
时间复杂度是 O(n)，空间复杂度是 O(1)。
腾讯云开发者
