Problem: 45. 跳跃游戏 II
题目描述
思路
Problem: 55.跳跃游戏
该题在上述的基础上，我们每次先求取当前可跳区间内的最远距离farthest;每当走到当前的区间胃部时（end == i）：跳跃步数加一(jumps++)，同时将下一次的可跳的最远区间更新(end = farthest;)
复杂度
时间复杂度:
O ( n ) O(n) O(n);其中 n n n为数组nums的大小
空间复杂度:文章来源：https://www.toymoban.com/news/detail-836118.html
O ( 1 ) O(1) O(1)文章来源地址https://www.toymoban.com/news/detail-836118.html
Code
class Solution {
public:
int jump(vector<int>& nums) {
int n = nums.size();
int end = 0;
int farthest = 0;
int jumps = 0;
for (int i = 0; i < n - 1; ++i) {
farthest = max(farthest, i + nums[i]);
if (end == i) {
jumps++;
end = farthest;
}
}
return jumps;
}
};
到了这里，关于力扣45. 跳跃游戏 II的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
