题目

• 给定一个非负数组，从第0个下标开始跳，能跳过的最大步长为这个下标对应的数组值，求问能不能从起始节点跳到数组的末尾。
• 举例，给定数组[2,3,1,4]，起始位置是在0，数组值为2，此时最大步长为2，那么可以调到下标1或者2，然后再根据对应的值的步长跳，最后可以到达下标为3的地方，返回true
  

解题方法（官方给出的解题步骤）

• 贪婪算法：这道题的最佳算法是采取贪心算法，给定一个lastPos是最大数组下标，然后从由到左走，假设它可以到达这个下标，那么此时就把下标赋值给右侧的值，然后迭代，直到循环结束，最后判断lastPos的值是否为0，即是起始值就可以得到答案

源代码实现

public class Solution {
    public boolean canJump(int[] nums) {
        int lastPos = nums.length - 1;
        for (int i = nums.length - 1; i >= 0; i--) {
            if (i + nums[i] >= lastPos) lastPos = i;
        }
        return lastPos == 0;
    }
}

解题思路2（从前往后）

• 上述思路给出的是从后往前查找的贪心算法，现在找出从前往后的贪心算法
• 首先我们假定一个当前能走到的最大值maxIndex,然后我们以这个为界进行遍历检查
• 遍历时随时更新maxIndex的值，maxIndex = max(maxIndex, i+nums[i])
• 如果在遍历过程中maxIndex > 数组长度就返回true，遍历完成都没有return，最后返回false

代码实现

public class Solution {
    public boolean canJump(int[] nums) {
        if(nums == null||nums.length == 0)
            return false;
        //初始化的maxindex值为nums[0];
        int maxIndex=nums[0];
        for(int i=0;i<=maxIndex;i++)
            {
            if(maxIndex>=nums.length-1)
                return true;
            maxIndex = Math.max(maxIndex, i+nums[i]);
        }
        return false;
    }
}