45. 跳跃游戏 II

Problem: 55. 跳跃游戏

思路

和55-跳跃游戏一样，我们在不断往前跳的过程中，可跳到的范围会越来越大。本题要求解的是跳到最后的最短次数，可以想到使用贪心的思想：对于i之后可以跳到的所有点，我们选择跳到能够到达范围最远的点，显然这样的跳跃（相对于本次选择的其他点）对于减少步数是最优的。不断遍历这个过程，直到能够到达最后点即可。

这样，我们只需要遍历一遍数组就能找到最少的跳跃次数。

复杂度

• 时间复杂度: $O(n)$：最多遍历一遍数组。
• 空间复杂度: $O(1)$：若干常量。

Code

class Solution {
    public int jump(int[] nums) {
        int n = nums.length;
        int ret = 0;
        int right = 0;
        int i = 0;
        while (i < n) {
            int now = right;
            if (now >= n - 1) return ret;
            while (i <= now) {
                right = Math.max(right, i + nums[i]);
                i++;
            }
            ret++;
        }
        return ret;
    }
}