力扣hot100：跳跃游戏

题目描述：

贪心算法思想：

贪心算法的核心是每一步都做出当前状态下的局部最优选择，最终期望得到全局最优解。对于本题，局部最优策略是：在遍历过程中，持续维护 “当前能到达的最大索引”，每到一个位置，就更新这个最大索引（取当前最大索引与 “当前位置 + 当前位置能跳的最大长度” 的较大值）。通过这种局部最优的更新，最终判断是否能覆盖到数组的最后一个索引。

思路解析：

要判断能否到达数组最后一个下标，关键在于跟踪 “能到达的最远位置”，具体思路如下：

1. 初始化最大可达索引：从数组第一个元素开始，初始最大可达索引为0（起始位置）。
2. 遍历数组的每个位置：
   • 若当前遍历的索引i超过了 “当前能到达的最大索引”，说明该位置无法到达，直接返回false。
   • 否则，更新 “能到达的最大索引”（取当前最大索引与i + nums[i]的较大值，i + nums[i]是从当前位置i能跳到的最远位置）。
   • 若更新后的最大索引已经覆盖了数组的最后一个下标（即maxLength >= n-1），直接返回true（提前终止，提升效率）。
3. 遍历结束：若顺利遍历完所有位置，说明最后一个下标可到达，返回true。

代码：

class Solution { public boolean canJump(int[] nums) { int n = nums.length; // 获取数组长度 if (n == 0) { // 处理空数组的边界情况 return false; } int maxLength = 0; // 记录当前能到达的最大索引 for (int i = 0; i < n; i++) { // 遍历数组的每个位置 // 若当前索引超过了能到达的最大范围，说明无法到达后续位置，返回false if (i > maxLength) { return false; } // 更新能到达的最大索引：取当前最大索引 与 “当前位置+当前位置能跳的最大长度”的较大值 maxLength = Math.max(maxLength, i + nums[i]); // 若最大索引已覆盖最后一个下标，直接返回true（提前终止） if (maxLength >= n - 1) { return true; } } return true; // 遍历完成后，说明最后一个下标可到达 } }

代码解析：

• 边界处理：if (n == 0)处理空数组场景，避免后续逻辑出错。
• 遍历与合法性判断：if (i > maxLength)是核心判断 —— 若当前位置i不在 “能到达的范围” 内，说明无法继续前进，直接返回false。
• 贪心更新最大可达索引：maxLength = Math.max(maxLength, i + nums[i])是贪心策略的体现 —— 每一步都尽可能扩大 “能到达的范围”，保证局部最优。
• 提前终止：if (maxLength >= n - 1)一旦最大范围覆盖了最后一个下标，立即返回true，无需遍历剩余元素，提升算法效率。