力扣第 55 题 跳跃游戏

力扣第 55 题 跳跃游戏（Jump Game）。题目要求判断一个非负整数数组中，是否能够从第一个位置跳跃到最后一个位置。每个元素表示从当前位置最多可以跳跃的步数。

解题思路

我们可以用 贪心算法 来解决这个问题。贪心的核心思想是始终维护当前能够到达的最远位置，并判断是否可以覆盖到数组的最后一个位置。

1. 初始化变量 maxReach 为 0，表示当前能够跳到的最远位置。
2. 遍历数组的每个位置 i，判断：
   • 如果当前下标 i 大于 maxReach，说明无法从前面的跳跃到达位置 i，返回 false。
   • 更新 maxReach 为 max(maxReach, i + nums[i])，表示当前能够跳到的最远位置。
3. 如果遍历结束后，maxReach 大于等于数组的最后一个下标，则返回 true。

---

C语言实现

#include <stdio.h>
#include <stdbool.h>// 跳跃游戏判断函数
bool canJump(int* nums, int numsSize) {int maxReach = 0;  // 能到达的最远位置for (int i = 0; i < numsSize; i++) {// 如果当前位置超过能到达的最远位置，说明无法继续跳跃if (i > maxReach) {return false;}// 更新能到达的最远位置if (i + nums[i] > maxReach) {maxReach = i + nums[i];}// 如果最远位置已经可以覆盖最后一个位置，则直接返回 trueif (maxReach >= numsSize - 1) {return true;}}return false;
}int main() {int nums[] = {2, 3, 1, 1, 4};int numsSize = sizeof(nums) / sizeof(nums[0]);if (canJump(nums, numsSize)) {printf("可以跳到最后一个位置！\n");} else {printf("无法跳到最后一个位置！\n");}return 0;
}

---

示例解析

示例 1:

输入：

int nums[] = {2, 3, 1, 1, 4};

输出：

可以跳到最后一个位置！

解释：

• 从第一个位置跳跃 2 步到索引 1，接着跳跃 3 步到最后一个位置。

示例 2:

输入：

int nums[] = {3, 2, 1, 0, 4};

输出：

无法跳到最后一个位置！

解释：

• 无论怎么跳跃，都无法跳过索引 3 的位置，因为索引 3 的值为 0。

---

复杂度分析

1. 时间复杂度：$O(n)$
   • 遍历数组中的每个元素一次，线性时间复杂度。
2. 空间复杂度：$O(1)$
   • 只使用了一个变量 maxReach，空间复杂度为常数。

---

贪心算法的核心

贪心的本质是：

• 只关心是否能到达尽可能远的位置，而不需要模拟实际的跳跃过程。
• 一旦 maxReach 无法覆盖某个位置，直接返回 false；如果能够覆盖到最后一个位置，返回 true。