力扣 跳跃游戏

每次更新目标位置时，实际上是在做一个局部的最优选择，选择跳跃能够到达当前目标位置的最远位置。因为每次更新目标位置时，都是基于当前能跳跃到的最远位置，因此最终的结果是全局最优的。

题目

从前往后遍历，更新可以到达的最远坐标，当最远坐标大于等于最后一个坐标即可到达，一旦当前坐标比最远坐标大，即更新的最远坐标达不到遍历的位置坐标。

时间复杂度 O(n)，空间复杂度O(1)。

class Solution {
    public boolean canJump(int[] nums) {
        //当前能到达的最远坐标
        int mx=0;
        for (int i = 0; i < nums.length; i++) {
            if(i>mx)return false;//若当前坐标大于最远坐标说明不能到达当前坐标，直接返回
                //若当前小于最远坐标，说明可以到达
                mx=Math.max(mx,i+nums[i]);//使用当前坐标的移动范围 更新能到达的最远坐标
        }
        return true;
    }
}

从后往前遍历， 设定一个指针为目标位置，当前位置能通过跳跃到达当前目标位置，就更新目标位置为当前位置，最终判断是否能回到起点。

时间复杂度 O(n)，空间复杂度O(1)。

class Solution {
    public boolean canJump(int[] nums) {
        int last = nums.length - 1;  // 目标位置是数组的最后一个位置
        for (int i = nums.length - 2; i >= 0; i--) {
            if (i + nums[i] >= last) {
                last = i;  // 如果当前位置能跳跃到目标位置，更新目标位置
            }
        }
        return last == 0;  // 如果最终目标位置是第一个位置，说明可以从起点到达终点
    }
}

这题仔细一看，数组中的每个元素都大于等于一时，一步一步走再慢也可以走到，而此时数组中的零可以看作一个坑，越过了便可到达。