力扣45. 跳跃游戏 II

Problem: 45. 跳跃游戏 II

题目描述

思路

Problem: 55.跳跃游戏

该题在上述的基础上，我们每次先求取当前可跳区间内的最远距离farthest;每当走到当前的区间胃部时（end == i）：跳跃步数加一(jumps++)，同时将下一次的可跳的最远区间更新(end = farthest;)

复杂度

时间复杂度:

$O(n)$;其中$n$为数组nums的大小

空间复杂度:

$O(1)$

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;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17