跳跃游戏 II · 峡谷跳跃救援

怎样从“nums=[2,3,1,1,4]：悬浮平台最多能跳多远，从 0 到传送门最少跃迁几次？”推导出 贪心 · 层扫描，并证明每次状态变化都不会漏掉答案？

中心结论：扫描当前跳覆盖层更新 farthest；i 到 curEnd 时 jumps++ 并把 curEnd 推进到 farthest。

给定一个非负整数数组，你最初位于数组的第一个位置。数组中的每个元素代表你在该位置可以跳跃的最大长度。你的目标是使用最少的跳跃次数到达数组的最后一个位置。

在本站主例中，nums=[2,3,1,1,4]：悬浮平台最多能跳多远，从 0 到传送门最少跃迁几次？

算法最终需要得到或观察：最少 2 次跃迁；curEnd 覆盖终点即结束。

枚举全部决策组合会指数爆炸；贪心只保留能被交换论证或支配关系证明更优的选择。

暴力方案的价值是确认题意并提供正确性基线。它通常会覆盖所有候选， 但没有保存已经确认的信息，因此同一状态会被重新计算。

1. 1建模把输入翻译成“局部最优路标”，明确答案需要观察什么。
2. 2状态只维护 jumps、curEnd（当前跳右边界）、farthest（下一跳最远边界）、扫描指针 i。
3. 3转移每一步按照 扫描当前跳覆盖层更新 farthest；i 到 curEnd 时 jumps++ 并把 curEnd 推进到 farthest。
4. 4收尾读取 最少 2 次跃迁；curEnd 覆盖终点即结束。，并复核边界与复杂度。

局部选择必须带着“替换任何其他选择都不会更差”的证明。

这道题不是为了记住一个组件名称，而是为了让状态具有可解释的语义：jumps、curEnd（当前跳右边界）、farthest（下一跳最远边界）、扫描指针 i。

要求找到最少跳跃次数，顺理成章的会想到用贪心算法解题。扫描步数数组，维护当前能够到达最大下标的位置，记为能到达的最远边界，如果扫描过程中到达了最远边界，更新边界并将跳跃次数 + 1。 扫描数组的时候，其实不需要扫描最后一个元素，因为在跳到最后一个元素之前，能到达的最远边界一定大于等于最后一个元素的位置，不然就跳不到最后一个元素，到达不了终点了；如果遍历到最后一个元素，说明边界正好为最后一个位置，最终跳跃次数直接 + 1 即可，也不需要访问最后一个元素。

扫描当前跳覆盖层更新 farthest；i 到 curEnd 时 jumps++ 并把 curEnd 推进到 farthest。

执行过程中持续维护：jumps、curEnd（当前跳右边界）、farthest（下一跳最远边界）、扫描指针 i。

正确性依赖以下不变量：在 curEnd 之前总能到达 farthest 覆盖的最远位置。

面试时可以压缩为：一趟贪心:更新 farthest,到 curEnd 换段 jumps++,O(n)。

落到当前题，执行机制可以压缩为：扫描当前跳覆盖层更新 farthest；i 到 curEnd 时 jumps++ 并把 curEnd 推进到 farthest。每一次更新都必须保持核心不变量，而不是只让样例碰巧得到正确答案。

1. 1题目与输入nums=[2,3,1,1,4]：悬浮平台最多能跳多远，从 0 到传送门最少跃迁几次？ 因为：扫描当前跳覆盖层更新 farthest；i 到 curEnd 时 jumps++ 并把 curEnd 推进到 farthest。
2. 2当前跳跃边界 curEnd 与下一跳 farthest最少跳跃 = 层数。 因为：每跳覆盖一层可达范围。
3. 3到达当前跳边界,jumps+1,farthest=2消耗一跳,更新边界。 因为：贪心选当前跳最远覆盖。
4. 4在跳内扩展 farthest=4扩展 farthest。 因为：贪心选当前跳最远覆盖。
5. 5到达当前跳边界,jumps+1,farthest=4消耗一跳,更新边界。 因为：贪心选当前跳最远覆盖。
6. 6在跳内扩展 farthest=4扩展 farthest。 因为：贪心选当前跳最远覆盖。
7. 7最少跳跃 2返回最少跳数。 因为：O(n) 贪心。
8. 8收尾与复杂度最少 2 次跃迁；curEnd 覆盖终点即结束。 因为：时间 O(n) · 空间 O(1)。扫描当前跳覆盖层更新 farthest；i 到 curEnd 时 jumps++ 并把 curEnd 推进到 farthest。

代码窗口不会按容易漂移的固定数字行号硬绑动画，而是根据当前语义阶段， 在完整 Go 实现中定位选择、计算、写回或返回分支。当前变量与高亮行一起变化。

func jump(nums []int) int {
	if len(nums) == 1 {
		return 0
	}
	needChoose, canReach, step := 0, 0, 0
	for i, x := range nums {
		if i+x > canReach {
			canReach = i + x
			if canReach >= len(nums)-1 {
				return step + 1
			}
		}
		if i == needChoose {
			needChoose = canReach
			step++
		}
	}
	return step
}

func main() {
    // 1. 主例
    //    输入：mode="jump-game-ii", nums=[2,3,1,1,4]
    //    期望：最少 2 次跃迁；curEnd 覆盖终点即结束。
    //
    // 2. 失败 / 未命中
    //    检查：BFS 也能做但 O(n) 贪心更轻。
    //
    // 3. 边界
    //    空输入、单元素、最小合法规模，以及答案恰好落在边界的情况。
    //
    // 4. 迁移
    //    LC55 跳跃游戏 I；LC130 被围区域
}

Go 参考实现基于 halfrost/LeetCode-Go 的 MIT 许可代码整理，并按本站教学结构补充解释与动画映射。

1. 1题意nums=[2,3,1,1,4]：悬浮平台最多能跳多远，从 0 到传送门最少跃迁几次？
2. 2重复枚举全部决策组合会指数爆炸；贪心只保留能被交换论证或支配关系证明更优的选择。
3. 3优化扫描当前跳覆盖层更新 farthest；i 到 curEnd 时 jumps++ 并把 curEnd 推进到 farthest。
4. 4证明在 curEnd 之前总能到达 farthest 覆盖的最远位置。
5. 5复杂度时间 O(n)，空间 O(1)