# 45. Jump Game II

You are given a 0-indexed array of integers `nums` of length `n`. You are initially positioned at `nums[0]`.

Each element `nums[i]` represents the maximum length of a forward jump from index `i`. In other words, if you are at `nums[i]`, you can jump to any `nums[i + j]` where:

• `0 <= j <= nums[i]` and
• `i + j < n`

Return the minimum number of jumps to reach`nums[n - 1]`. The test cases are generated such that you can reach `nums[n - 1]`.

Example 1:

``````Input: nums = [2,3,1,1,4]
Output: 2
Explanation: The minimum number of jumps to reach the last index is 2. Jump 1 step from index 0 to 1, then 3 steps to the last index.
``````

Example 2:

``````Input: nums = [2,3,0,1,4]
Output: 2
``````

Constraints:

• `1 <= nums.length <= 10^4`
• `0 <= nums[i] <= 1000`
• It’s guaranteed that you can reach `nums[n - 1]`.

``````class Solution {
public:
int jump(vector<int>& nums) {
int res = 0, n = nums.size(), i = 0, cur = 0;
while (cur < n - 1) {
++res;
int pre = cur;
for (; i <= pre; ++i) {
cur = max(cur, i + nums[i]);
}
if (pre == cur) return -1; // May not need this
}
return res;
}
};
``````

``````class Solution {
public:
int jump(vector<int>& nums) {
int res = 0, n = nums.size(), last = 0, cur = 0;
for (int i = 0; i < n - 1; ++i) {
cur = max(cur, i + nums[i]);
if (i == last) {
last = cur;
++res;
if (cur >= n - 1) break;
}
}
return res;
}
};
``````

Github 同步地址：

https://github.com/grandyang/leetcode/issues/45

Jump Game

Jump Game III

Jump Game IV

Jump Game V

Jump Game VIII

Minimum Number of Visited Cells in a Grid

Maximum Number of Jumps to Reach the Last Index

Visit Array Positions to Maximize Score

https://leetcode.com/problems/jump-game-ii/

https://leetcode.com/problems/jump-game-ii/discuss/18028/O(n)-BFS-solution

https://leetcode.com/problems/jump-game-ii/discuss/18023/Single-loop-simple-java-solution

LeetCode All in One 题目讲解汇总(持续更新中…)

（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，快快加入吧～）

|

Venmo 打赏

—|—

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation