贪心
贪心地按层扩展：当前能到达的最远位置为 right，在走到 right 之前记录下一层能到达的最远位置 newRight。当 i 到达 right 时，步数加一，并把边界推进到 newRight。
时间复杂度
空间复杂度
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| class Solution {
public int jump(int[] nums) {
int ans = 0, n = nums.length, right = 0, newRight = 0;
for (int i = 0; i < n; ++i) {
if (right >= n - 1) {
break;
}
newRight = Math.max(newRight, i + nums[i]);
if (i == right) {
right = newRight;
ans++;
}
}
return ans;
}
}
|