GuilinDev
Lc0045
05 August 2008
45 Jump Game II
原题概述
Given an array of non-negative integers, you are initially positioned at the first index of the array.
Each element in the array represents your maximum jump length at that position.
Your goal is to reach the last index in the minimum number of jumps.
Example:
1
2
3
4
Input: [2,3,1,1,4]
Output: 2
Explanation: The minimum number of jumps to reach the last index is 2.
Jump 1 step from index 0 to 1, then 3 steps to the last index.
Note:
You can assume that you can always reach the last index.
题意和分析
上一道题55 Jump Game是判断能否到达最后，这一道题是找出步数最少的走法；
LC的讨论里面，大部分都是贪婪算法的思路（其实也是一维数组的BFS），每次在可跳范围内选择可以使得跳的更远的位置。
如下图，开始的位置是 2，可跳的范围是橙色的。然后因为 3 可以跳的更远，所以选择跳到 3 的位置。
然后现在的位置就是 3 了，能跳的范围是橙色的，然后因为 4 可以跳的更远，所以选择下次跳到 4 的位置。
So on and so forth，写代码时用curFarthest 表示当前能跳的最远边界，对于上边的的例子，第一个图就是橙色 1，第二个图中就是橙色的 4，遍历数组的时候，遇到了边界，就重新更新新的边界直到最后。
代码
Greedy，时间O(n)，空间O(1)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public int jump(int[] nums) {
int currEnd = 0; // 当前数能达到的最远距离
int steps = 0; // 返回结果
int currFar = 0; // 当前数和之前一起考虑所能达到的最远距离
for (int i = 0; i <= nums.length - 1; i++) { // 检查每一个数的最大跳力
if (i > currEnd) {//当前已有的(上个数贡献的)跳力已尽（边界已到），需要再跳一次去当前能达到的最远边界currFar
currEnd = currFar;
steps++;
}
// 每遇到一个新数就，就判断一下最远可以跳到的距离
currFar = Math.max(currFar, nums[i] + i);
}
return steps;
}
}