题解 | #跳跃游戏(三)#贪心解法
跳跃游戏(三)
https://www.nowcoder.com/practice/d92a70f4f42248d688b93c9e50d2e757
假设数组长度为n:
- 如果n等于0,则可以直接返回-1
- 如果n等于1,则可以直接返回0
- 当n大于0的时候,走第一步最远可以到达v[0]的索引位置,当我们要走到v[0]的索引位置的时候应该要走第二步,假设正整数k属于在区间[0,i],那么当v[k]+k取最大值的时候,也就是我们第二步从索引为k的位置起跳可以到达最远的位置。依次类推,我们使用len表示走step步的时候可以到达的最远距离,然后当len <= i的时候,我们要走第step+1步,此时选择[0,i]区间中能使v[k]+k取最大值的索引作为下一次起跳的位置,由于我们每次遍历的时候是可以计算每个v[i]+i的值,我们可以使用一个计数器来存放该值
时间复杂度:O(N),空间复杂度O(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) { len = std::max(next, v[i] + i); step++; } else { next = std::max(next, v[i] + i); } if (len <= i) { return -1; } // 其实,这里可以判断len是否大于等于n-1,如果满足则可以跳出循环 } return step; } int main() { int n; std::cin >> n; std::vector<int> v(n); for (int i = 0; i < n; ++i) { std::cin >> v[i]; } std::cout << solve(v) << std::endl; return 0; }