LeetCode——跳跃游戏II

NO.45 跳跃游戏II 困难

思路一：贪心算法 nums[i]表示的可以跳入的最大范围，如果当前nums[i]所能跳到的范围不涉及重点，那么就在当前能跳到的范围内选择一个最优的点(可以跳出更远的范围的点)，因为如果这个最优点都不能跳到终点，那么其他的点更不能跳到。

这种每一步都选择最优来保证最终结果的最优性的方法就是典型的贪心算法。

public int jump(int[] nums) {
    //end当前能跳到的最远点，steps跳的步数，maxposition能跳的最远的距离
    int end=0,steps=0,maxPosition=0;
    //注意是：i<length-1，如果最后一跳最远距离刚好到达终点会导致额外一次steps++
    for (int i = 0; i < nums.length - 1; i++) {
        //在当前可跳的范围内，寻找能跳的最远位置
        maxPosition=Math.max(maxPosition,nums[i]+i);
        //到达当前跳跃最远点
        if (i == end) {
            end=maxPosition;
            steps++;
        }
    }
    return steps;
}

时间复杂度：O(n)

---

本人菜鸟，有错误请告知，感激不尽！

更多题解和学习记录博客:博客、github