贪心
解题思路
局部最优：每次取最大跳跃步数（取最大覆盖范围）；
整体最优：最后得到整体最大覆盖范围，看是否能到终点；
不用考虑每一步跳跃到哪个位置，而是尽可能的跳跃到最远的位置，看最多能覆盖的位置，不断更新能覆盖的距离；
那么这个问题就转化为跳跃覆盖范围究竟可不可以覆盖到终点，每次移动只能在 cover 的范围内移动，每移动一个元素 cover 得到该元素数值（新的覆盖范围）的补充，让 i 继续移动下去；
图解
复杂度
-
时间复杂度：
O(n)，其中 n 是数组的长度； -
空间复杂度：
O(1)；
代码实现
var canJump = function (nums) {
// 长度为 1 直接就是终点
if (nums.length === 1) return true;
// 能覆盖的最远距离
let cover = 0;
for (let i = 0; i <= cover; i++) {
// 当前覆盖距离 cover 和当前位置加能跳跃的距离中取一个较大者
cover = Math.max(cover, i + nums[i]);
// 覆盖距离超过或等于 nums.length - 1 说明能到达终点
if (cover >= nums.length - 1) return true;
}
// 循环完成之后，还没返回 true 就是不能达到终点
return false;
};
打赏作者
您的打赏是我前进的动力
微信
支付宝
leetcode🧑💻 53. 最大子数组和
上一篇
评论
