企业官网建设流程全解析

LeetCode 45. 跳跃游戏 II的 TypeScript 实现，最优解法是使用贪心算法。

算法思路

这道题的核心思想是“在每一步的跳跃范围内，选择能跳到的最远位置作为下一步的边界”，从而最小化跳跃次数。

具体维护三个变量：

• steps：记录跳跃次数。
• currentEnd：当前跳跃步数能到达的最远边界。
• farthest：在当前跳跃范围内，所有点能跳到的最远位置。

遍历过程：

1. 遍历数组（注意：不需要遍历最后一个元素，因为到达终点后无需再跳跃）。
2. 在遍历过程中，不断更新 farthest，即 Math.max(farthest, i + nums[i])。
3. 当遍历到当前边界 currentEnd 时，说明当前跳跃步数已用完，必须进行下一次跳跃：
   • 跳跃次数 steps 加 1。
   • 将当前边界 currentEnd 更新为 farthest。
4. 遍历结束后返回 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) 仅使用了常数级别的额外空间（几个变量）

关键细节与易错点

1. 遍历范围是 n - 1：
   循环条件必须是 i < n - 1。因为题目保证可以到达终点，当我们遍历到终点前一个元素时，如果触发了边界更新，说明已经可以一步跳到终点。如果遍历最后一个元素，可能会多算一次无意义的跳跃。

2. 为什么贪心策略有效？
   贪心的关键在于：我们不需要知道具体跳到哪个具体位置，只需要知道在当前的“跳跃额度”内，最远能覆盖到哪里。当走到边界时，说明当前的跳跃额度用完了，此时我们选择之前探索过的能跳得最远的那个点作为下一跳，这保证了每一步都是“最有远见”的选择。

3. 提前终止优化：
   在 currentEnd = farthest 之后，加上 if (currentEnd >= n - 1) break; 可以在已经能到达终点时提前退出循环，避免后续不必要的遍历，在实际运行中能有效降低耗时。

需要我顺带把这道题的动态规划（DP）解法也写出来吗？虽然 DP 解法时间复杂度较高（O(n^2)），但有助于对比理解贪心算法的精妙之处。