45.跳跃游戏II

题目描述

题解

详细请看注释，就是遍历，一步走然后这一步里面看，这一步里面走过的路中，哪个下一步能走的更远，就选哪个位置为下一步

代码

class Solution {
    public int jump(int[] nums) {
        int ans = 0;
        int n = nums.length;
        // 一开始是从数组0开始跳的
        // 所以end maxPos初始化为0
        int end = 0;
        int maxPos = 0;
        // 因为最后一个可以不用跳 (我们的目的就是到达数组最后一个位置
        for (int i = 0; i < n-1; i++) {
            // 这里的maxPos就是它能跳的距离位置最大值 当i等于这个maxPos的时候(这是这一步所能跳到最远)
            // 更新能跳到最远的位置,然后再进行下一步
            maxPos = Math.max(nums[i] + i, maxPos);
            if (i == end) {
                // end 下一步的终点
                end = maxPos;
                ans++;
            }
        }
        return ans;
    }
}