LeetCode 45. 跳跃游戏 II的 TypeScript 实现最优解法是使用贪心算法。算法思路这道题的核心思想是“在每一步的跳跃范围内选择能跳到的最远位置作为下一步的边界”从而最小化跳跃次数。具体维护三个变量steps记录跳跃次数。currentEnd当前跳跃步数能到达的最远边界。farthest在当前跳跃范围内所有点能跳到的最远位置。遍历过程遍历数组注意不需要遍历最后一个元素因为到达终点后无需再跳跃。在遍历过程中不断更新 farthest即 Math.max(farthest, i nums[i])。当遍历到当前边界 currentEnd 时说明当前跳跃步数已用完必须进行下一次跳跃跳跃次数 steps 加 1。将当前边界 currentEnd 更新为 farthest。遍历结束后返回 steps。TypeScript 代码实现function jump(nums: number[]): number {const n nums.length;// 如果数组长度小于等于1说明已经在终点不需要跳跃if (n 1) return 0;let steps 0; // 记录跳跃次数 let currentEnd 0; // 当前跳跃步数能到达的最远边界 let farthest 0; // 在当前跳跃范围内下一步能到达的最远位置 // 遍历数组跳过最后一个元素因为到达终点后无需再跳 for (let i 0; i n - 1; i) { // 更新在当前范围内能跳到的最远位置 farthest Math.max(farthest, i nums[i]); // 如果到达了当前跳跃的边界说明必须进行一次新的跳跃 if (i currentEnd) { steps; currentEnd farthest; // 更新下一次跳跃的边界 // 优化如果新边界已经覆盖终点可以提前结束遍历 if (currentEnd n - 1) break; } } return steps;}复杂度分析维度 复杂度 说明时间复杂度 O(n) 只需对数组进行一次线性遍历每个元素仅访问一次空间复杂度 O(1) 仅使用了常数级别的额外空间几个变量关键细节与易错点遍历范围是 n - 1循环条件必须是 i n - 1。因为题目保证可以到达终点当我们遍历到终点前一个元素时如果触发了边界更新说明已经可以一步跳到终点。如果遍历最后一个元素可能会多算一次无意义的跳跃。为什么贪心策略有效贪心的关键在于我们不需要知道具体跳到哪个具体位置只需要知道在当前的“跳跃额度”内最远能覆盖到哪里。当走到边界时说明当前的跳跃额度用完了此时我们选择之前探索过的能跳得最远的那个点作为下一跳这保证了每一步都是“最有远见”的选择。提前终止优化在 currentEnd farthest 之后加上 if (currentEnd n - 1) break; 可以在已经能到达终点时提前退出循环避免后续不必要的遍历在实际运行中能有效降低耗时。需要我顺带把这道题的动态规划DP解法也写出来吗虽然 DP 解法时间复杂度较高O(n^2)但有助于对比理解贪心算法的精妙之处。