面试知识库

45. 跳跃游戏 II#

今天让我们继续深入探讨跳跃游戏的进阶版本。在第一个版本中，我们只需要判断能否到达终点，而这次我们要找出到达终点的最少跳跃次数。这个问题看似简单，但其中蕴含着更深层的思考。让我们一起揭开它的神秘面纱！

📚 从生活场景理解#

想象你在玩一个跳石头过河的游戏。河面上有一系列石头，每块石头上都标着一个数字，表示你站在这块石头上最远能跳多远。你想用最少的跳跃次数到达对岸。这就像在规划旅程，每一步都要考虑如何让整体路径最优。

问题描述#

题目目标#

给定一个长度为 n 的非负整数数组 nums ，你最初位于第一个下标。数组中的每个元素表示你在该位置可以跳跃的最大长度。请返回到达最后一个下标的最少跳跃次数。

示例 1#

输入： nums = [2,3,1,1,4] 输出： 2 说明： 把输入和输出放在一起看，会更容易直接抓住题目要求的变化。

💡 问题的精髓#

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

举个例子：

输入：nums = [2,3,1,1,4]
输出：2
解释：跳到最后一个位置的最小跳跃数是 2：
     跳 1 步，从下标 0 到 1
     跳 1 步，从下标 1 到 4
java

📝 深入理解解题思路#

这道题的美妙之处在于它的贪心策略。让我们通过一个形象的比喻来理解：

想象你在玩”跳格子”游戏，但每次跳跃时你都要思考两件事：

  1. 这一跳能直接到达的范围（currentMaxReach）
  2. 在这个范围内起跳，下一跳最远能到哪里（nextMaxReach）

🎨 让我们用图来理解这个过程#

🎯 关键思考点#

让我们深入理解这个解法的几个关键点：

  1. 为什么需要维护两个边界？ 这是这个解法的精髓。currentMaxReach告诉我们当前这一跳能到哪里，而nextMaxReach则在探索下一跳的可能性。这就像是在探索地图时，既要知道当前位置，又要看看远处的风景。

  2. 贪心策略的正确性 在每个可达区间内，我们都选择能跳得最远的位置作为下一跳的目标。这个策略之所以是最优的，是因为：如果存在一个跳得更少的方案，那么它一定也能被我们的贪心策略覆盖到。

  3. 边界条件的处理 注意我们的遍历只需要到达倒数第二个位置，因为一旦能够到达最后一个位置，就不需要再跳了。这是一个重要的优化。

🌟 代码的优化思路#

  1. 空间优化 我们只需要几个变量就可以完成整个算法，空间复杂度为O(1)。

  2. 时间优化 通过维护两个边界，我们避免了重复计算，时间复杂度为O(n)。

  3. 提前结束 一旦发现当前可达范围已经覆盖了终点，就可以立即结束遍历。

💡 举一反三#

这种贪心策略还可以应用在其他类似的问题上：

  1. 带体力值的跳跃游戏
// 每次跳跃消耗体力值，求到达终点的最小体力值消耗
public int minEnergyJump(int[] nums, int[] energy) {
    // 类似的思路，但需要考虑体力值的消耗
    // 一般会在“最远可达范围”之外再维护“到达该点的最小代价”状态
}
java
  1. 带障碍物的跳跃游戏
// 某些位置有障碍物不能跳到，求最少跳跃次数
public int jumpWithObstacles(int[] nums, boolean[] obstacles) {
    // 需要在更新nextMaxReach时考虑障碍物
    // 例如：当 obstacles[i] 为 true 时，当前位置不可作为落点或起跳点
}
java

🎓 题目带来的启示#

这道题目给我们的启示是：

  1. 有时候，看似需要动态规划的问题，用贪心策略可能会有更优雅的解法。

  2. 在解决问题时，维护多个状态（这里是两个边界）可能会让问题变得更清晰。

  3. 优化代码时，要注意观察是否存在可以提前结束的条件。

这道题不仅教会我们一个解决特定问题的方法，更重要的是展示了如何通过维护多个状态来简化问题的复杂度。如果你对这个话题还有任何疑问，欢迎在评论区讨论！