題目：
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.
For example:
Given array A = [2,3,1,1,4]
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.)
思路：貪心例嘱，將題目轉(zhuǎn)移為計(jì)算 step步數(shù)能達(dá)到的最遠(yuǎn)距離迹恐。
代碼：https://leetcode.com/discuss/72370/java-solution-with-explanation
public class Solution {
public int jump(int[] nums) {
// If nums.length < 2, means that we do not
// need to move at all.
if (nums == null || nums.length < 2) {
return 0;
}
// First set up current region, which is
// from 0 to nums[0].
int l = 0;
int r = nums[0];
// Since the length of nums is greater than
// 1, we need at least 1 step.
int step = 1;
// We go through all elements in the region.
while (l <= r) {
// If the right of current region is greater
// than nums.length - 1, that means we are done.
if (r >= nums.length - 1) {
return step;
}
// We should know how far can we reach in current
// region.
int max = Integer.MIN_VALUE;
for (; l <= r; l++) {
max = Math.max(max, l + nums[l]);
}
// If we can reach far more in this round, we update
// the boundary of current region, and also add a step.
if (max > r) {
l = r + 1;
r = max;
step++;
}
}
// We can not finish the job.
return -1;
}
}
