题解 | #跳跃游戏(三)#贪心解法，O（N）时间复杂度
如有帮助，欢迎点赞~~
假设数组长度为n：
- 如果n等于0,则可以直接返回-1
- 如果n等于1,则可以直接返回0
- 当n大于0的时候，走第一步最远可以到达v[0]的索引位置，当我们要走到v[0]+1的索引位置的时候应该要走第二步，假设正整数k属于区间[0,i]，那么当v[k]+k取最大值的时候，也就是我们第二步从索引为k的位置起跳可以到达最远的位置。依次类推，我们使用len表示走step步的时候可以到达的最远距离，然后当len <= i的时候，我们要走step+1步，此时选择[0,i]区间中能使v[k]+k取最大值的索引作为下一次起跳的位置，由于我们每次遍历的时候是可以计算每个v[i]+i的值得，因此我们可以使用一个计数器来存放该值。在需要下一跳的时候更新step+1最远能到达的位置。
int solve(const std::vector<int> &v)
{
if (v.size() == 0)
{
return -1;
}
if (v.size() == 1)
{
return 0;
}
int len = v[0]; // 走1步的时候可以最远到达的索引位置
int next = len; // 用于记录[0,v[0]+1]区间中v[k]+k的最大值
int step = 1; // 最少要走的步数
for (int i = 1; i < v.size() - 1; ++i)
{
if (len <= i)// 走step步无法到达索引为i的位置，此时需要再走一步
{
len = std::max(next, v[i] + i);// 下一最远可到达位置为
step++;
}
else
{
next = std::max(next, v[i] + i);// 表示在0~len范围内，如果再选一个位置i为起跳点，最远可以到达的位置
}
if (len <= i)
{
return -1;
}
// 其实，这里可以判断len是否大于等于n-1，如果满足则可以跳出循环
}
return step;
}
