力扣AC：跳跃游戏II - 贪心算法

题目链接

跳跃游戏II

题目描述

实现代码

思路：由题意可以知道无论怎么走最终都能够走到最后一个下标，因此可以使用贪心算法的思想，每一步都尽量在下一步选择范围内走的最远，如下是反向查找的实现代码：

class Solution {
    public int jump(int[] nums) {
        int position = nums.length - 1;
        int steps = 0;
        while (position > 0) {
            for (int i = 0; i < position; i++) {
                if (i + nums[i] >= position) {
                    position = i;
                    steps++;
                    break;
                }
            }
        }
        return steps;
    }
}

反向查找代码容易理解，因为使用了两层循环，而我们还可以通过正向查找的方式，将另一层循环得到的数据直接通过变量的形式保存，而减少一层循环，实现代码如下：

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