LeetCode题解：跳跃游戏

题目描述

给定一个非负整数数组nums，你最初位于数组的第一个下标。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能到达最后一个下标。

示例

• 示例1
  输入：nums = [2,3,1,1,4]
  输出：true
  解释：可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。
• 示例2
  输入：nums = [3,2,1,0,4]
  输出：false
  解释：无论怎样，总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 ， 所以永远不可能到达最后一个下标。

方法思路

首先以示例1为例nums = [2,3,1,1,4]

• 我们一开始在位置 0，可以跳跃的最大长度为 2，因此最远可以到达的位置被更新为 2；
• 我们遍历到位置 1，由于 1≤2，因此位置 1 可达。我们用 1 加上它可以跳跃的最大长度 3，将最远可以到达的位置更新为 4。由于 4 大于等于最后一个位置 4，因此我们直接返回 True。

再来看示例2，nums = [3,2,1,0,4]

• 我们一开始在位置 0，可以跳跃的最大长度为 3，因此最远可以到达的位置被更新为 3；
• 我们遍历到位置 1，由于 1≤3，因此位置 1可达，加上它可以跳跃的最大长度 2 得到 3，没有超过最远可以到达的位置；
• 位置 2、位置 3 同理，最远可以到达的位置不会被更新；
• 我们遍历到位置 4，由于 4>3，因此位置 4 不可达，我们也就不考虑它可以跳跃的最大长度了。
• 遍历完成后，4位置仍然无法到达，所以返回false。

class Solution {
    public boolean canJump(int[] nums) {
        int n = nums.length;
        int maxStep = 0;
       for(int i=0;i<n;i++){
           if(i<=maxStep){
                maxStep = Math.max(maxStep,i+nums[i]);
                if(maxStep>=n-1){
                    return true;
                }
           }   
       }
       return false; 
    }
}

复杂度分析

• 时间复杂度：O(n)，其中n为数组的大小。只需要访问nums数组一遍共n个位置。
• 空间复杂度：O(1)，不需要额外的空间开销。