# 0055. 跳跃游戏
### 题目地址(55. 跳跃游戏)
### 题目描述
```
给定一个非负整数数组，你最初位于数组的第一个位置。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个位置。
示例 1:
输入: [2,3,1,1,4]
输出: true
解释: 我们可以先跳 1 步，从位置 0 到达 位置 1, 然后再从位置 1 跳 3 步到达最后一个位置。
示例 2:
输入: [3,2,1,0,4]
输出: false
解释: 无论怎样，你总会到达索引为 3 的位置。但该位置的最大跳跃长度是 0 ， 所以你永远不可能到达最后一个位置。
```
### 前置知识
* [贪心](https://github.com/azl397985856/leetcode/blob/master/thinkings/greedy.md)
### 公司
* 阿里
* 腾讯
* 百度
* 字节
### 思路
这道题目是一道典型的`贪心`类型题目。思路就是用一个变量记录当前能够到达的最大的索引，并逐个遍历数组中的元素去更新这个索引，遍历完成判断这个索引是否大于`数组长度 - 1`即可。
我在[贪心](https://github.com/azl397985856/leetcode/blob/master/thinkings/greedy.md)的专题中，讲到了这道题的升级版，大家可以去看一下。
### 关键点解析
* 记录和更新当前位置能够到达的最大的索引
### 代码
* 语言支持: Javascript,C++,Java,Python3
Javascript Code:
```js
/**
* @param {number[]} nums
* @return {boolean}
*/
var canJump = function (nums) {
let max = 0; // 能够走到的数组下标
for (let i = 0; i < nums.length; i++) {
if (max < i) return false; // 当前这一步都走不到，后面更走不到了
max = Math.max(nums[i] + i, max);
}
return max >= nums.length - 1;
};
```
C++ Code:
```
class Solution {
public:
bool canJump(vector& nums) {
int n=nums.size();
int k=0;
for(int i=0;ik){
return false;
}
// 能跳到最后一个位置
if(k>=n-1){
return true;
}
// 从当前位置能跳的最远的位置
k = max(k, i+nums[i]);
}
return k >= n-1;
}
};
```
Java Code:
```java
class Solution {
public boolean canJump(int[] nums) {
int n=nums.length;
int k=0;
for(int i=0;ik){
return false;
}
// 能跳到最后一个位置
if(k>=n-1){
return true;
}
// 从当前位置能跳的最远的位置
k = Math.max(k, i+nums[i]);
}
return k >= n-1;
}
}
```
Python3 Code:
```
class Solution:
def canJump(self, nums: List[int]) -> bool:
"""思路同上"""
_max = 0
_len = len(nums)
for i in range(_len-1):
if _max < i:
return False
_max = max(_max, nums[i] + i)
# 下面这个判断可有可无，但提交的时候数据会好看点
if _max >= _len - 1:
return True
return _max >= _len - 1
```
***复杂度分析***
* 时间复杂度：$O(N)$
* 空间复杂度：$O(1)$
大家对此有何看法，欢迎给我留言，我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库： 。 目前已经 37K star 啦。 大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。 
---
# Agent Instructions: Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.
Perform an HTTP GET request on the current page URL with the `ask` query parameter:
```
GET https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/medium/55.jump-game.md?ask=
```
The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.
Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.