55. Jump Game

题目分析

纪念一下，解出来的第一道击败100%其他答案的题目_{，给自己鼓个掌，继续努力}

代码

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

class Solution {
    public boolean canJump(int[] nums) {
        if(nums == null || nums.length == 0) return false;
        if(nums.length == 1) return true;
        if(nums.length == 2 && nums[0] != 0) return true;
        // 从倒数第二个位置向前扫描
        boolean ans = false;
        int pos = nums.length - 1;
        if(nums[nums.length - 2] == 0) {
            ans = false;
        } else {
            ans = true;
            // 记录最近的一个能跳过去的位置
            pos = nums.length - 2;
        }
        for(int i = nums.length - 3; i >= 0; i--) {
            // 如果相邻的下一个结点跳不到最后
            if(ans == false) {
                // 判断一下从当前位置能不能跳到上一个能跳到最后结点的位置
                if(nums[i] >= pos - i) {
                    // 记录最后一个能跳到最后结点的位置
                    pos = i;
                    ans = true;
                } else {
                    ans = false;
                }
            } else {
                if(nums[i] >= 1) {
                    ans = true;
                    pos = i;
                } else {
                    ans = false;
                }
            }
        }
        return ans;
    }
}