题目描述
给你一个非负整数数组 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 <= 10^4
- 0 <= nums[i] <= 10^5
问题分析
这是一个经典的贪心算法问题。问题的关键在于判断是否能从起点跳到终点，而不是求解具体的跳跃路径。
当我们站在某个位置时，可以选择跳1步、2步...直到该位置的最大跳跃长度。但实际上，我们不需要考虑具体跳几步，而是关注能否覆盖到终点。
解题思路
贪心算法
贪心算法的核心思想是：每一步都计算能跳到的最远距离，只要能覆盖到最后一个位置，就说明可以到达。
具体步骤如下：
- 维护一个变量 maxReach，表示当前能到达的最远位置
- 遍历数组中的每个元素，如果当前位置已经超过了能到达的最远位置，说明无法到达该位置，返回 false
- 否则，更新 maxReach 为当前位置能到达的最远位置和已记录的最远位置中的较大值
- 如果 maxReach 已经覆盖了最后一个位置，可以直接返回 true
动态规划方法
虽然贪心算法是解决此问题的最优解，但我们也可以使用动态规划来理解这个问题：
- 创建一个布尔数组 dp，其中 dp[i] 表示是否能到达位置 i
- 初始条件：dp[0] = true（起点总是可以到达的）
- 对于每个可达位置 i，标记从该位置可以跳到的所有位置 j 为可达（dp[j] = true）
- 最终检查 dp[n-1] 是否为 true
算法过程
以示例1为例：nums = [2,3,1,1,4]
使用贪心算法的执行过程：
- 初始位置：i = 0，maxReach = 0
- 遍历位置0：nums[0] = 2，更新 maxReach = max(0, 0+2) = 2
- 遍历位置1：nums[1] = 3，更新 maxReach = max(2, 1+3) = 4（已覆盖终点，可返回true）
- 实际上已经可以确定能到达终点了，但我们继续遍历以展示完整过程
- 遍历位置2：nums[2] = 1，更新 maxReach = max(4, 2+1) = 4
- 遍历位置3：nums[3] = 1，更新 maxReach = max(4, 3+1) = 4
- 遍历位置4：nums[4] = 4，更新 maxReach = max(4, 4+4) = 8
最终 maxReach = 8 大于等于 nums.length - 1 = 4，返回 true。
详细代码实现
Java 实现 - 贪心算法
class Solution {
public boolean canJump(int[] nums) {
// 当前能到达的最远位置
int maxReach = 0;
// 遍历数组
for (int i = 0; i < nums.length; i++) {
// 如果当前位置已经超过了能到达的最远位置，说明无法到达该位置
if (i > maxReach) {
return false;
}
// 更新最远可以到达的位置
maxReach = Math.max(maxReach, i + nums[i]);
// 如果最远位置已经覆盖了最后一个位置，可以直接返回true
if (maxReach >= nums.length - 1) {
return true;
}
}
// 如果能够遍历完整个数组，说明最后一个位置是可达的
return true;
}
}C# 实现 - 贪心算法
public class Solution {
public bool CanJump(int[] nums) {
// 当前能到达的最远位置
int maxReach = 0;
// 遍历数组
for (int i = 0; i < nums.Length; i++) {
// 如果当前位置已经超过了能到达的最远位置，说明无法到达该位置
if (i > maxReach) {
return false;
}
// 更新最远可以到达的位置
maxReach = Math.Max(maxReach, i + nums[i]);
// 如果最远位置已经覆盖了最后一个位置，可以直接返回true
if (maxReach >= nums.Length - 1) {
return true;
}
}
// 如果能够遍历完整个数组，说明最后一个位置是可达的
return true;
}
}Java 实现 - 动态规划
class Solution {
public boolean canJump(int[] nums) {
int n = nums.length;
// dp[i]表示是否能到达位置i
boolean[] dp = new boolean[n];
// 起点总是可达的
dp[0] = true;
for (int i = 0; i < n; i++) {
// 如果当前位置不可达，跳过
if (!dp[i]) {
continue;
}
// 从当前位置可以跳到的所有位置
for (int j = 1; j <= nums[i] && i + j < n; j++) {
dp[i + j] = true;
}
// 如果最后一个位置已经标记为可达，可以提前返回
if (dp[n - 1]) {
return true;
}
}
return dp[n - 1];
}
}C# 实现 - 动态规划
public class Solution {
public bool CanJump(int[] nums) {
int n = nums.Length;
// dp[i]表示是否能到达位置i
bool[] dp = new bool[n];
// 起点总是可达的
dp[0] = true;
for (int i = 0; i < n; i++) {
// 如果当前位置不可达，跳过
if (!dp[i]) {
continue;
}
// 从当前位置可以跳到的所有位置
for (int j = 1; j <= nums[i] && i + j < n; j++) {
dp[i + j] = true;
}
// 如果最后一个位置已经标记为可达，可以提前返回
if (dp[n - 1]) {
return true;
}
}
return dp[n - 1];
}
}复杂度分析
贪心算法
- 时间复杂度：O(n)，其中 n 是数组长度，只需要遍历一次数组。
- 空间复杂度：O(1)，只使用了常数个额外变量。
动态规划
- 时间复杂度：O(n²)，最坏情况下，对于每个位置，我们都需要考虑跳跃的所有可能性。
- 空间复杂度：O(n)，需要一个长度为 n 的数组记录状态。