当前位置： 面试刷题>> 跳跃游戏(经典算法150题)
### 题目描述：
**跳跃游戏（Jump Game）**
给定一个非负整数数组 `nums`，你最初位于数组的第一个位置。数组中的每个元素代表你在该位置可以跳跃的最大长度。判断你是否能够到达数组的最后一个位置。
例如，给定数组 `nums = [2,3,1,1,4]`，从位置 0 开始，你可以跳到位置 2（因为 `nums[0]` 是 2），然后从位置 2 你可以跳到位置 3，从位置 3 你可以跳到位置 4（因为 `nums[3]` 是 1，虽然它不大于 3，但足够你跳到位置 4）。因此，返回 `true`。
### 解题思路：
这个问题可以通过贪心算法来解决。我们从左到右遍历数组，同时维护一个变量（比如叫 `farthest`），它表示在当前位置能够到达的最远距离。每当我们遇到一个位置 `i`，我们更新 `farthest` 为 `max(farthest, i + nums[i])`，即当前能到达的最远距离和从当前位置 `i` 跳跃后能达到的最远距离中的较大值。如果 `farthest` 在任何时候都不小于数组的长度减一（即最后一个位置的索引），那么我们就可以到达数组的最后一个位置，返回 `true`；如果遍历完数组都没有达到这个条件，则返回 `false`。
### PHP 示例代码：
```php
function canJump($nums) {
$n = count($nums);
$farthest = 0;
for ($i = 0; $i < $n - 1; $i++) { // 注意这里只需要遍历到倒数第二个元素
$farthest = max($farthest, $i + $nums[$i]);
if ($farthest < $i) { // 如果当前能到达的最远距离连自己都跳不过去，则提前结束
return false;
}
}
return true;
}
```
### Python 示例代码：
```python
def canJump(nums):
farthest = 0
for i in range(len(nums) - 1): # 同样，只需要遍历到倒数第二个元素
farthest = max(farthest, i + nums[i])
if farthest <= i: # 如果当前能到达的最远距离连自己都跳不过去，则提前结束
return False
return True
```
### JavaScript 示例代码：
```javascript
function canJump(nums) {
let farthest = 0;
for (let i = 0; i < nums.length - 1; i++) { // 遍历到倒数第二个元素
farthest = Math.max(farthest, i + nums[i]);
if (farthest <= i) { // 如果当前能到达的最远距离连自己都跳不过去，则提前结束
return false;
}
}
return true;
}
```
这些代码示例都使用了贪心算法来解决跳跃游戏问题，通过维护一个 `farthest` 变量来跟踪当前能够到达的最远距离，从而判断是否能够到达数组的最后一个位置。