55. 跳跃游戏
给你一个非负整数数组 nums ，你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个下标，如果可以，返回 true ；否则，返回 false 。
示例 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.length <= 1040 <= nums[i] <= 105
解答
class Solution {
public boolean canJump(int[] nums) {
int mx = 0;
for (int i = 0; i< nums.length;i++) {
if (i > mx) { // 最远可到距离mx小于i,无法到达i
return false;
}
mx = Math.max(mx, i+nums[i]); // 可以到达i，就再用i的对应nums[i]值与当前mx比较，更新最大可到距离mx
}
return true;
}
}
题意：从 i 可以跳到闭区间 [i,i+nums i ] 中的任意整数。问：能不能从 0 跳到 n−1？
先看示例 2，nums=[3,2,1,0,4]。我们在遍历数组的同时，维护最右可以到达的位置 mx，如下表：
从 0 可以跳到 1,2,3，但是无法从 1,2,3 中的任何位置跳到 4。当我们遍历到 i=4 时，发现 i>mx
这意味着 i 是无法到达的，返回 false。
然后来看示例 1，nums=[2,3,1,1,4]，在遍历数组的同时，维护最远可以到达的位置 mx，如下表：
从 0 可以跳到 1,2，最远可以到达的位置 mx=2。能否跳到更远的位置？那就看从 1 能跳到哪些位置，从 2 能跳到哪些位置。
从 1 可以跳到 2,3,4，mx 更新成 4。
从 2 可以跳到 3，mx 不变。
从 3 可以跳到 4，mx 不变。
到达 4，返回 true。
一般地，算法如下：
从左到右遍历 nums，同时维护能跳到的最远位置 mx，初始值为 0。
如果 i>mx，说明无法跳到 i，返回 false。
否则，用 i+nums i更新 mx 的最大值。
如果循环中没有返回 false，那么最后返回 true。
另一种理解方式是，把每个 nums i看成闭区间 [i,i+nums i]，问题变成判定这 n 个区间能否合并成一个大区间（而不是多个区间），这可以用 56. 合并区间 的 算法 解决。
class Solution {
public boolean canJump(int[] nums) {
int mx = 0;
for (int i = 0; i < nums.length; i++) {
if (i > mx) { // 无法到达 i
return false;
}
mx = Math.max(mx, i + nums[i]); // 从 i 最右可以跳到 i + nums[i]
}
return true;
}
}
也可以在 mx≥n−1 时就返回 true，这可以让我们提前退出循环。
class Solution {
public boolean canJump(int[] nums) {
int mx = 0;
for (int i = 0; mx < nums.length - 1; i++) {
if (i > mx) { // 无法到达 i
return false;
}
mx = Math.max(mx, i + nums[i]); // 从 i 最右可以跳到 i + nums[i]
}
return true;
}
}
复杂度分析
时间复杂度：O(n)，其中 n 是 nums 的长度。
空间复杂度：O(1)。
作者：灵茶山艾府
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。