45. Jump Game II

Given an array of non-negative integers nums, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Your goal is to reach the last index in the minimum number of jumps.

You can assume that you can always reach the last index.

设置一个当前可以访问的最大范围limit,在遍历中对其进行更新。
和当前可访问位置中的最远距离end,每次访问到达end时,计算步数。

遍历数组,比较limit和当前i能访问的最远距离i+nums[i],保留较大值。
当i达到end时,更新end为之前记录的可访问最远距离limit。步数+1。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public int jump(int[] nums) {
int count = 0;
int limit = 0;
int end = 0;

for(int i = 0; i < nums.length-1; i++){
limit = Math.max(limit, i + nums[i]);
if(i == end){
end = limit;
count++;
}
}

return count;
}
}
Author

Xander

Posted on

2022-04-28

Updated on

2022-04-27

Licensed under

Comments