跳跃游戏Ⅱ

题目链接

45.跳跃游戏Ⅱ

解题思路

每次贪心最大覆盖值，同时更新步数

代码实现

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

复杂度

时间复杂度: $O(n)$
空间复杂度: $O(1)$