45. 跳跃游戏 II
题目描述
输入长度为 n 的整数数组 nums，下标从 0 开始。你一开始站在下标 0。
站在下标 i 时，一次可以向后跳 j 格，其中 0 <= j <= nums[i]，并且落点 i + j 不能超出数组。
返回跳到下标 n - 1 所需的最少次数。题目保证一定能跳到。
示例 1
输入：nums = [2,3,1,1,4] 输出：2
解释：先从下标 0 跳 1 格到下标 1，再跳 3 格到末尾，共 2 次。
示例 2
输入：nums = [2,3,0,1,4] 输出：2
解释：同样是 0 → 1 → 4，共 2 次。
数据范围
1 <= nums.length <= 10^40 <= nums[i] <= 1000- 一定能到达下标
n - 1。
解题思路：正向贪心（按层扩展边界）
把一跳能覆盖的区间视作一层，扫描到当前层末尾时跳一次，并把边界更新为下一层最远处。
为什么正确
扫描到 current_end 前，steps 次跳跃覆盖的范围已确定；farthest 是下一跳可达最远处。
复杂度分析
时间 O(n)，空间 O(1)。
易错点
循环不必在末尾再次加跳；只在到达当前层边界时计数。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
from typing import List
class Solution:
def jump(self, nums: List[int]) -> int:
steps = 0
current_end = 0
farthest = 0
for i in range(len(nums) - 1):
farthest = max(farthest, i + nums[i])
if i == current_end:
steps += 1
current_end = farthest
return stepsclass Solution {
public int jump(int[] nums) {
int steps = 0;
int currentEnd = 0;
int farthest = 0;
for (int i = 0; i < nums.length - 1; i++) {
farthest = Math.max(farthest, i + nums[i]);
if (i == currentEnd) {
steps++;
currentEnd = farthest;
}
}
return steps;
}
}class Solution {
public:
int jump(vector<int>& nums) {
int steps = 0;
int current_end = 0;
int farthest = 0;
for (int i = 0; i < (int)nums.size() - 1; i++) {
farthest = max(farthest, i + nums[i]);
if (i == current_end) {
steps++;
current_end = farthest;
}
}
return steps;
}
};func jump(nums []int) int {
steps := 0
currentEnd := 0
farthest := 0
for i := 0; i < len(nums)-1; i++ {
farthest = max(farthest, i+nums[i])
if i == currentEnd {
steps++
currentEnd = farthest
}
}
return steps
}var jump = function(nums) {
let steps = 0;
let currentEnd = 0;
let farthest = 0;
for (let i = 0; i < nums.length - 1; i++) {
farthest = Math.max(farthest, i + nums[i]);
if (i === currentEnd) {
steps++;
currentEnd = farthest;
}
}
return steps;
};function jump(nums: number[]): number {
let steps = 0;
let currentEnd = 0;
let farthest = 0;
for (let i = 0; i < nums.length - 1; i++) {
farthest = Math.max(farthest, i + nums[i]);
if (i === currentEnd) {
steps++;
currentEnd = farthest;
}
}
return steps;
};其他解法
反向贪心每步从左扫描找最远的上一跳起点，O(n²)；正向贪心把每一跳能覆盖的区间看成一层，一次扫描完成，O(n)。
解法 2：反向贪心查找出发位置 时间 O(n²)，空间 O(1)
从终点倒推：当前目标位置为 pos，从左往右找第一个能一步跳到 pos 的下标 i，把它作为上一跳的出发点，令 pos = i 并计数加一。重复直到 pos 回到 0。选最靠左的出发点是贪心的关键：它离起点最近，后续需要的跳数不会更多。
思路直观、容易证明，但每次都要从头扫描，最坏 O(n²)（例如全为 1 的数组），在 n 较大时会明显慢于正向按层扩展的 O(n) 解法。
from typing import List
class Solution:
def jump(self, nums: List[int]) -> int:
pos = len(nums) - 1
steps = 0
while pos > 0:
for i in range(pos):
if i + nums[i] >= pos:
pos = i
steps += 1
break
return stepsclass Solution {
public int jump(int[] nums) {
int pos = nums.length - 1, steps = 0;
while (pos > 0) {
for (int i = 0; i < pos; i++) {
if (i + nums[i] >= pos) {
pos = i;
steps++;
break;
}
}
}
return steps;
}
}class Solution {
public:
int jump(vector<int>& nums) {
int pos = nums.size() - 1, steps = 0;
while (pos > 0) {
for (int i = 0; i < pos; i++) {
if (i + nums[i] >= pos) {
pos = i;
steps++;
break;
}
}
}
return steps;
}
};func jump(nums []int) int {
pos, steps := len(nums)-1, 0
for pos > 0 {
for i := 0; i < pos; i++ {
if i+nums[i] >= pos {
pos = i
steps++
break
}
}
}
return steps
}var jump = function(nums) {
let pos = nums.length - 1, steps = 0;
while (pos > 0) {
for (let i = 0; i < pos; i++) {
if (i + nums[i] >= pos) {
pos = i;
steps++;
break;
}
}
}
return steps;
};function jump(nums: number[]): number {
let pos = nums.length - 1, steps = 0;
while (pos > 0) {
for (let i = 0; i < pos; i++) {
if (i + nums[i] >= pos) {
pos = i;
steps++;
break;
}
}
}
return steps;
}