当前位置：首页 > news >正文

LeetCode 45.跳跃游戏II：贪心策略下的最少跳跃次数求解

news 2025/8/19 5:37:46

一、问题定义与核心挑战

1.1 问题描述

给定一个非负整数数组 nums，你最初位于数组的第一个下标。数组中的每个元素 nums[i] 表示你在该位置可以跳跃的最大长度。你的目标是使用最少的跳跃次数到达数组的最后一个下标。假设你总能到达数组的最后一个下标。

1.2 核心特征与难点

最优性要求：不仅要判断可达性，还要找到最少跳跃次数
跳跃规则：从位置 i 可跳到 i+1 至 i+nums[i] 之间的任意位置
贪心选择：如何在每一步选择最优的跳跃点以最小化总次数

示例：

输入：nums = [2,3,1,1,4]
输出：2（最优路径：0→1→4，两次跳跃）

二、解题思路：基于覆盖范围的贪心策略

2.1 核心思想

通过跟踪当前覆盖范围和下一步最大覆盖范围，在每次到达当前覆盖范围的边界时进行跳跃，从而保证每次跳跃都是最优的：

当前覆盖范围（cover）：当前跳跃所能到达的最远位置
下一步最大覆盖范围（maxCover）：在当前覆盖范围内，所有位置能到达的最远位置
跳跃时机：当遍历到当前覆盖范围的边界时，必须进行一次跳跃，此时将当前覆盖范围更新为下一步最大覆盖范围

2.2 直观理解

把跳跃过程想象成多阶段冲刺：

第一阶段：从起点出发，能到达的范围是 [0, cover]，在这个范围内寻找能跳得最远的点，确定下一阶段的最大范围 maxCover
当到达第一阶段的边界（i = cover）时，必须跳一次，进入第二阶段，此时 cover 更新为 maxCover
重复上述过程，直到覆盖范围包含终点

三、代码逐行解析

3.1 边界条件处理

if (nums.length == 1) {return 0;  // 只有一个元素时，无需跳跃
}

3.2 核心变量定义

int cover = 0;       // 当前覆盖范围的边界
int maxCover = 0;    // 下一步能到达的最大覆盖范围
int cnt = 0;         // 跳跃次数

3.3 遍历与跳跃逻辑

for (int i = 0; i < nums.length; i++) {// 持续更新下一步能到达的最大覆盖范围maxCover = Math.max(i + nums[i], maxCover);// 当到达当前覆盖范围的边界，且能跳得更远时if (i == cover && maxCover > cover) {cover = maxCover;  // 更新覆盖范围cnt++;             // 跳跃次数加1// 若已覆盖终点，提前返回if (cover >= nums.length - 1) {return cnt;}}
}

3.4 返回结果

return cnt;

四、算法执行过程演示

以 nums = [2,3,1,1,4] 为例：

索引 `i`	当前元素 `nums[i]`	`maxCover` 计算	关键操作	`cover`	`cnt`
0	2	max(0+2=2, 0) = 2	-	0	0
1	3	max(1+3=4, 2) = 4	-	0	0
2	1	max(2+1=3, 4) = 4	i=2 == cover=0？不	0	0
3	1	max(3+1=4, 4) = 4	i=3 == cover=0？不	0	0
4	4	max(4+4=8, 4) = 8	i=4 == cover=0？是 maxCover>cover → 更新 cover=4，cnt=1 cover≥4（终点）→ 返回 1？	4	1

注意：实际执行中，当 i=2 时已经满足 i==cover（0），此时会触发跳跃：

在 i=2 时，i==cover（0）且 maxCover=4>0 → cover=4，cnt=1
此时 cover=4 已包含终点（4），直接返回 cnt=1？

修正演示：

i=0 时，maxCover=2
i=1 时，maxCover=4
i=2 时，i==cover（0）→ 触发跳跃，cover=4，cnt=1，此时 cover≥4 → 返回 1

最终结果为 2？不，正确结果应为 2，这里需要更精确的步骤分析：

正确步骤：

初始状态：cover=0，maxCover=0，cnt=0
i=0：
- maxCover = max(0+2, 0) = 2
- i != cover（0==0），但需判断是否更新
- 此时 i==cover 且 maxCover>cover → cover=2，cnt=1
i=1：
- maxCover = max(1+3=4, 2) =4
i=2：
- icover（22）
- maxCover=4>2 → cover=4，cnt=2
- 此时 cover≥4（终点）→ 返回 2