跳跃游戏：从贪心思维中寻找最优解！
大家好，我是忍者算法。今天让我们一起探讨一个非常有趣的问题 - 跳跃游戏。这道题不仅考察我们的编程能力，更重要的是训练我们的贪心思维。让我们像玩游戏一样，一步步揭开它的奥秘！
📚 游戏化理解
想象你正在玩一个跳跃游戏：你站在一条数字路径的起点，每个位置都标着一个数字，表示你在这个位置最多可以向前跳几步。你的目标是判断能否跳到终点。这就像是在玩跳房子，但每个格子都有自己的规则！
💡 问题的本质
具体来说，给你一个非负整数数组 nums，每个位置的数字代表你在这个位置可以跳跃的最大长度。判断你是否能够从数组的第一个位置跳到最后一个位置。
例如：
输入：[2,3,1,1,4]
输出：true
解释：可以先跳1步到达索引1，然后再从索引1跳3步到达最后一个位置。
输入：[3,2,1,0,4]
输出：false
解释：无论如何，总会到达索引为3的位置，这里只能跳0步，卡住了。class Solution {
public boolean canJump(int[] nums) {
// 记录当前能够到达的最远位置
int maxReach = 0;
// 遍历数组中的每个位置
// 注意：我们只需要遍历到当前能到达的最远位置
for (int i = 0; i <= maxReach && i < nums.length; i++) {
// 更新最远可达位置
// 当前位置i + 在位置i能跳跃的最大距离nums[i]
maxReach = Math.max(maxReach, i + nums[i]);
// 如果已经能够到达最后一个位置，立即返回true
if (maxReach >= nums.length - 1) {
return true;
}
}
// 如果循环结束还没有返回true，说明无法到达最后一个位置
return false;
}
// 一个更直观但功能相同的版本
public boolean canJumpAlternative(int[] nums) {
// 把最远可达距离想象成能量值
int energy = nums[0];
// 只要还有能量，就继续往前走
for (int i = 1; i < nums.length; i++) {
// 每走一步，消耗一点能量
energy--;
// 如果能量耗尽，就无法继续前进
if (energy < 0) {
return false;
}
// 来到新位置，更新能量值（取当前剩余能量和新获得能量的较大值）
energy = Math.max(energy, nums[i]);
}
// 如果能走完全程，返回true
return true;
}
}📝 解题思路详解
让我们深入理解这个贪心算法的精髓：
1. 核心思想
我们不需要真的去尝试所有可能的跳跃路径。相反，我们只需要关注"能跳到多远"这个问题。如果我们能跳到的最远距离超过了数组末尾，那就一定能达到目标。
2. 贪心策略
在遍历数组时，我们持续更新"最远可达距离"。每到达一个新位置，就结合当前位置的跳跃能力，更新最远可达距离。这就像是在不断收集和更新我们的"能量值"。
🎨 让我们通过图解来理解
<svg viewBox="0 0 800 400" xmlns="http://www.w3.org/2000/svg">
<!-- 背景 -->
<rect width="800" height="400" fill="#f8f9fa"/>
<!-- 标题 -->
<text x="400" y="40" text-anchor="middle" font-size="20" fill="#1976d2">跳跃游戏可视化</text>
<!-- 数字格子 -->
<g transform="translate(100,100)">
<!-- 格子背景 -->
<rect x="0" y="0" width="100" height="100" fill="#2196f3" opacity="0.2"/>
<rect x="120" y="0" width="100" height="100" fill="#2196f3" opacity="0.2"/>
<rect x="240" y="0" width="100" height="100" fill="#2196f3" opacity="0.2"/>
<rect x="360" y="0" width="100" height="100" fill="#2196f3" opacity="0.2"/>
<rect x="480" y="0" width="100" height="100" fill="#2196f3" opacity="0.2"/>
<!-- 数字 -->
<text x="50" y="60" text-anchor="middle" font-size="30" fill="#1976d2">2</text>
<text x="170" y="60" text-anchor="middle" font-size="30" fill="#1976d2">3</text>
<text x="290" y="60" text-anchor="middle" font-size="30" fill="#1976d2">1</text>
<text x="410" y="60" text-anchor="middle" font-size="30" fill="#1976d2">1</text>
<text x="530" y="60" text-anchor="middle" font-size="30" fill="#1976d2">4</text>
<!-- 跳跃路径 -->
<path d="M 50 80 C 100 50, 150 50, 170 80"
fill="none" stroke="#4caf50" stroke-width="3"/>
<path d="M 170 80 C 250 20, 350 20, 530 80"
fill="none" stroke="#4caf50" stroke-width="3"/>
<!-- 起点和终点标记 -->
<circle cx="50" cy="80" r="5" fill="#4caf50"/>
<circle cx="530" cy="80" r="5" fill="#f44336"/>
</g>
<!-- 说明文字 -->
<g transform="translate(100,250)">
<text x="0" y="0" font-size="14">最远可达距离的变化：</text>
<text x="0" y="30" font-size="14">位置0：2步 → 可达位置2</text>
<text x="0" y="60" font-size="14">位置1：3步 → 可达位置4</text>
<text x="0" y="90" font-size="14">成功到达终点！</text>
</g>
</svg>🎯 关键思考点
为什么用贪心算法？ 贪心算法在这里特别有效，因为我们只关心"能否到达"，而不是"最优路径"。每一步都取最大可能的范围，如果最大范围都到不了，其他选择更不可能到达。
能量值的理解 可以把跳跃能力想象成"能量值"：每走一步消耗一点能量，每个位置可以补充能量（取当前剩余能量和新能量的较大值）。
优化细节 注意到一旦我们发现能到达终点，就可以立即返回true，不需要继续遍历。这是一个很好的优化。
🌟 面试技巧
当在面试中遇到这道题时，你可以这样展示你的思维过程：
首先说明贪心的思路： "我们不需要尝试所有路径，只需要维护一个最远可达距离。"
解释代码的关键部分： "maxReach表示当前能到达的最远位置，我们不断更新它。"
分析复杂度：
- 时间复杂度：O(n)，只需要遍历一次数组
- 空间复杂度：O(1)，只需要一个变量记录状态
💡 扩展思考
这道题还有一些有趣的变种：
- 最少跳跃次数
// 计算到达终点需要的最少跳跃次数
public int minJumps(int[] nums) {
int jumps = 0;
int currentMax = 0;
int nextMax = 0;
for (int i = 0; i < nums.length - 1; i++) {
nextMax = Math.max(nextMax, i + nums[i]);
if (i == currentMax) {
jumps++;
currentMax = nextMax;
}
}
return jumps;
}- 跳跃游戏 III 当你可以向前或向后跳固定步数时，判断是否能到达值为0的位置。这需要用BFS或DFS来解决。
🎓 启发与思考
这道题给我们的启发是：
有时候，我们不需要求出所有可能的路径，只需要关注能否达到目标。
贪心算法虽然简单，但在很多场景下都能得到最优解。
把抽象的问题具象化（比如想象成能量值）有助于我们理解问题的本质。
作者：忍者算法 公众号：忍者算法 🎁 回复【刷题清单】获取LeetCode高频面试题合集 🧑💻 回复【代码】获取多语言完整题解 💡 回复【加群】加入算法交流群，一起进步 #算法面试 #LeetCode #贪心算法 #动态规划
这道题教会我们：有时候最简单的思路反而是最优的解法。贪心算法虽然不是总能得到最优解，但在特定问题上却能发挥惊人的效果。如果你对这个话题还有任何疑问，欢迎在评论区讨论！