力扣45. 跳跃游戏 II

Problem: 45. 跳跃游戏 II

题目描述

思路

1.获取数组的长度len，定义int类型变量end用于标记每次在当前可以跳到的最远距离，farthest用于记录每次可以跳跃到的最远距离，jumps用于记录最小的跳跃次数；
2.从0 ~ len遍历nums，并每次更新farthest（farthest = max(nums[i] + i, farthest);），若走到了当前可以跳跃到的最远距离，则更新end（end = farthest;），并使jump++，若当end >= len - 1时则直接返回jumps即可

复杂度

时间复杂度:

$O(n)$；其中$n$是数组nums的长度；

空间复杂度:

$O(1)$

Code

class Solution {
public:/*** Greedy algorithm* * @param nums Given array* @return int*/int jump(vector<int>& nums) {if (nums.size() < 2) {return 0;}int len = nums.size();int end = 0;int farthest = 0;int jumps = 0;for (int i = 0; i < len; ++i) {farthest = max(nums[i] + i, farthest);if (end == i) {jumps++;end = farthest;}if (end >= len - 1) {return jumps;}}return jumps;}
};