55. 跳跃游戏
给你一个非负整数数组 nums ，你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个下标，如果可以，返回 true ；否则，返回 false 。
示例 1：
输入：nums = [2,3,1,1,4]
输出：true
解释：可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。
示例 2：
输入：nums = [3,2,1,0,4]
输出：false
解释：无论怎样，总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 ， 所以永远不可能到达最后一个下标。
提示：
- 1 <= nums.length <= 104
- 0 <= nums[i] <= 105
贪心
每一次都更新最大的步数
这段代码是用于解决“跳跃游戏”问题的C++实现，下面是对这段代码的详细注释：
class Solution {
public:
bool canJump(vector<int>& nums) {
int coust = nums[0]; // 初始化当前能跳到的最远距离为数组的第一个元素
// 如果第一个元素为0且数组不是只有一个元素，则无法到达最后一个下标，直接返回false
if(coust == 0 && nums[nums.size()-1] != 0) return false;
// 从数组的第二个元素开始遍历
for(int i = 1; i < nums.size(); i++) {
// 更新当前能跳到的最远距离。比较当前位置能跳的距离nums[i]和前一步剩余的跳跃力coust-1的较大值
coust = max(nums[i], coust-1);
// 如果在非数组末尾位置coust已经减到0，说明无法再向前跳跃，返回false
if(i != nums.size()-1 && coust == 0)
return false;
}
// 如果能顺利遍历完数组，说明可以到达最后一个下标，返回true
return true;
}
};
解题思路总结：
- 初始化：利用变量
coust来记录从当前位置起能够跳跃到的最远距离，初始值为数组的第一个元素nums[0]。 - 特殊情况处理：如果
nums[0]为0且数组长度大于1（即非只有一个元素），意味着无法移动，因此直接返回false。 - 遍历数组：从索引1开始遍历数组，对于每一个位置，更新
coust为在当前位置能跳的距离nums[i]与coust-1中的较大值。这里coust-1代表从前一个位置跳到当前位置后，剩下的最远跳跃距离。 - 判断是否能继续跳跃：在遍历过程中，如果在非数组末尾位置发现
coust已经为0，意味着不能再向前进，因此返回false。 - 遍历完成：如果能遍历完整个数组，意味着可以跳到最后或超过最后的位置，因此返回
true。
通过这种方法，代码高效地解决了“跳跃游戏”的问题，它的时间复杂度为O(n)，因为只需要遍历一次数组。
取最大跳跃步数（取最大覆盖范围）
刚看到本题一开始可能想：当前位置元素如果是 3，我究竟是跳一步呢，还是两步呢，还是三步呢，究竟跳几步才是最优呢？
其实跳几步无所谓，关键在于可跳的覆盖范围！
不一定非要明确一次究竟跳几步，每次取最大的跳跃步数，这个就是可以跳跃的覆盖范围。
这个范围内，别管是怎么跳的，反正一定可以跳过来。
那么这个问题就转化为跳跃覆盖范围究竟可不可以覆盖到终点！
每次移动取最大跳跃步数（得到最大的覆盖范围），每移动一个单位，就更新最大覆盖范围。
贪心算法局部最优解：每次取最大跳跃步数（取最大覆盖范围），整体最优解：最后得到整体最大覆盖范围，看是否能到终点。
局部最优推出全局最优，找不出反例，试试贪心！
如图：
i 每次移动只能在 cover 的范围内移动，每移动一个元素，cover 得到该元素数值（新的覆盖范围）的补充，让 i 继续移动下去。
而 cover 每次只取 max(该元素数值补充后的范围, cover 本身范围)。
如果 cover 大于等于了终点下标，直接 return true 就可以了。
C++代码如下：
class Solution {
public:
bool canJump(vector<int>& nums) {
if(nums.size() == 1) return true; // 如果数组只包含一个元素，那么已经在最后一个下标，返回true
int cover = 0; // 初始化可以到达的最远下标为0
// 遍历数组，但只遍历到当前能覆盖的最远距离
for(int i = 0; i <= cover; i++) {
// 更新能到达的最远下标，是当前位置加上该位置能跳的最远长度，和之前的cover中的较大值
cover = max(i + nums[i], cover);
// 如果更新后的cover已经能覆盖到数组的最后一个位置或更远，返回true
if(cover >= nums.size() - 1)
return true;
}
// 如果遍历结束后，cover未能覆盖到数组的最后一个位置，返回false
return false;
}
};
解题思路总结：
- 特殊情况处理：当数组只有一个元素时，显然已经在最后一个下标，因此直接返回
true。 - 初始化覆盖距离：用
cover变量来记录当前可以到达的最远下标，初始值为0。 - 遍历数组：通过一个循环遍历数组，但只遍历到当前
cover所能到达的最远距离。这是因为如果当前位置超过了cover能到达的范围，说明这个位置是不可达的。 - 更新覆盖距离：在每个位置，尝试更新
cover。计算当前位置i加上nums[i]（从当前位置能跳的最远距离）与cover的较大值，来更新cover。 - 判断是否能到达末尾：在这个过程中，如果
cover的值大于等于数组的最后一个下标，意味着可以到达最后，因此返回true。 - 遍历结束：如果循环结束时，
cover的值未能覆盖到数组的最后一个下标，则说明不能到达末尾，返回false。
这种方法的优点是运行效率高，因为它的时间复杂度为O(n)，只需遍历一次数组即可。通过不断更新可以到达的最远距离，这种贪心算法简洁而有效地解决了问题。
