贪心
解题思路
局部最优：当前可移动距离尽可能多走，如果还没到终点，步数再加一；
整体最优：一步尽可能多走，从而达到最少步数；
解题思路大体与 leetcode🧑💻 55. 跳跃游戏 一致，唯一不同的是需要确定什么时候跳跃次数加一；
- 如果某一个作为 起跳点 的格子可以跳跃 2 个距离，那么表示后面 2 个格子都可以作为 起跳点 ，可以对每一个能作为 起跳点 的格子都尝试跳一次，把 能跳到最远的距离 不断更新；
- 如果从这个 起跳点 起跳叫做第 1 次 跳跃，那么从后面 2 个格子起跳 都 可以叫做第 2 次 跳跃；
- 由于第 1 次 跳跃 能跳到最远的距离 是 2 个距离，在未走到 第三个格子 前需要不断计算下一次跳跃 能跳到最远的距离；
- 当走完第 1 次 跳跃 2 个距离后，跳跃次数 +1 并更新下一次 能跳到最远的距离；
- 重复以上步骤，直到循环结束；
图解
复杂度
-
时间复杂度：
O(n)，其中 n 是数组长度； -
空间复杂度：
O(1)；
代码实现
var jump = function (nums) {
let step = 0; // 记录跳跃的次数
let currPosEnd = 0; // 使用 currPosEnd 记录这次跳跃的边界，到达边界就跳跃次数 + 1
let maxPos = 0; // 能跳到最远的距离
// 循环次数为 nums.length - 1，可以避免跳跃次数多加了一次
for (let i = 0; i < nums.length - 1; i++) {
// 一直向后寻找跳跃最远的位置
maxPos = Math.max(maxPos, i + nums[i]);
// 判断当前是不是跳跃的边界，到达跳跃边界后更新步数、跳跃边界
if (i === currPosEnd) {
currPosEnd = maxPos; // 更新边界
step++;
}
}
return step;
};
打赏作者
您的打赏是我前进的动力
微信
支付宝
leetcode🧑💻 55. 跳跃游戏
上一篇
评论
