跳跃游戏 II

原题链接

使用的方法

• 贪心算法

解题思路

本题可以使用贪心算法来解决。
我们维护两个变量：end 表示当前能够到达的最远位置，maxPos 表示在当前范围内能够到达的最远位置。
遍历数组，更新 maxPos，当遍历到 end 时，说明需要进行一次跳跃，更新 end 为 maxPos，并增加跳跃次数。

代码实现

class Solution {
    public int jump(int[] nums) {
        int end = 0;
        int maxPos = 0;
        int steps = 0;
        for (int i = 0; i < nums.length -1; i++){
            maxPos = Math.max(maxPos,nums[i] + i);
            if(i == end){
                end = maxPos;
                steps++;
            }
        }
        return steps;
    }
}