【LeetCode热题100】-- 45.跳跃游戏II

45.跳跃游戏II

方法：贪心

在具体的实现中，维护当前能够到达的最大下标的位置，记为边界。从左到右遍历数组，到达边界时，更新边界并将跳跃次数加一

在遍历数组时，不访问最后一个元素，因为在访问最后一个元素之前，我们的边界一定大于等于最后一个位置，否则就无法跳到最后一个位置了。

class Solution {
    public int jump(int[] nums) {
        int n = nums.length;
        int maxPosition = 0,steps = 0,end = 0;
        for(int i = 0;i < n - 1;i++){
            maxPosition = Math.max(maxPosition, i + nums[i]);  //下次最远能跳多远
            if( i == end ){
                end = maxPosition;  //更新下一次跳的位置
                steps++;  //本次跳跃的所有位置都检查过了，跳跃一次
            }
        }
        return steps;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14