跳跃游戏II

难度：中等

题目描述

给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。 每个元素 nums[i] 表示从索引 i 向前跳转的最大长度。换句话说，如果你在 nums[i] 处，你可以跳转到任意 nums[i + j] 处:

• 0 <= j <= nums[i]
• i + j < n

返回到达 nums[n - 1] 的最小跳跃次数。生成的测试用例可以到达 nums[n - 1]。

示例1

输入：nums = [2,3,1,1,4] 输出：2

示例2

输入：nums = [2,3,0,1,4] 输出：2

题解

使用贪心算法计算到达下标 $n-1$ 的最小跳跃次数

用 $currentJumps$ 表示当前跳跃次数，用 $currentMaxPosition$ 和 $nextMaxPosition$ 分别表示跳跃次数 $currentJumps$ 能够到达的最远距离和跳跃次数 $currentJumps+1$ 可以到达的最远距离，初始时 $currentJumps=0，currentMaxPosition=0，nextMaxPosition=0$

从左到右遍历数组 $nums$，对每个 $0\leq i<n$，执行如下操作：

• 如果 $i>currentMaxPosition$，则下标 $i$ 超出跳跃次数 $currentJumps$ 可以到达的下标，因此到达下标 $i$ 的最小跳跃次数是 $currentJumps+1$，需要更新 $currentJumps$ 和 $currentMaxPosition$ 的值；将 $currentJumps$ 的值加1，将 $currentMaxPosition$ 的值更新为 $nextMaxPosition$。如果 $i\leq currentMaxPosition$，则不执行更新操作
• 从下标 $i$ 可以到达的最大下标为 $i+nums[i]$。由于跳跃次数 $currentJumps$ 可以到达下标 $i$，因此跳跃次数 $currentJumps+1$ 可以到达下标 $i+nums[i]$，跳跃次数 $currentJumps+1$ 可以到达的最大下标不小于 $i+nums[i]$，用 $i+nums[i]$更新 $nextMaxPosition$ 的值

遍历结束之后，$currentJumps$ 即为到达下标 $n-1$ 的最小跳跃次数

想法代码

class Solution
{
    public static void Main(String[] args)
    {
        int[] nums = { 2, 3, 1, 1, 4 };
        Solution solution = new Solution();
        int res = solution.Jump(nums);
        Console.WriteLine(res);
    }

    public int Jump(int[] nums)
    {
        int currentJumps = 0;
        int currentMaxPosition = 0;
        int nextMaxPosition = 0;
        int len = nums.Length;
        for (int i = 0; i < len; i++)
        {
            if (i > currentMaxPosition)
            {
                currentJumps++;
                currentMaxPosition = nextMaxPosition;
            }
            nextMaxPosition = Math.Max(nextMaxPosition, nums[i] + i);
        }
        return currentJumps;
    }
}