贪心算法解决带长度参数的跳跃问题。

题目链接-来源：力扣（LeetCode）

给你一个非负整数数组 nums ，你最初位于数组的第一个位置。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

你的目标是使用最少的跳跃次数到达数组的最后一个位置。

假设你总是可以到达数组的最后一个位置。

示例 1:

输入: nums = [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2。
  从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。

思路：

此题容易想到较为简单的 O(n²) 复杂度算法，我们用一个数组 jumps[] 记录第 i 格距离起点所需的跳步数。对于我们遍历到的第 i 格，其跳步数为 jumps[i]，我们维护 第 i 格之后的 nums[i] 格。显然，这些格子的跳步数至多为 jumps[i] + 1。设置初始条件为 jumps[0] = 0，最终返回 jumps[n - 1] 即可。
以上做法，我们可能对每一个位置进行了多次更新，考虑能否优化到 O(n) 复杂度。
我们用 jump 记录到当前位置所需的跳跃次数，用一个变量 bound 记录当前位置跳跃所能达到的最大范围，bound 就是每一位置的坐标 i 与可跳跃距离 nums[i] 的和 i + nums[i]。当我们还没跨过某个 bound 时，我们都不需要更新 jump，所以我们用另一个变量 end 标注尚未跨过的这个旧的 bound， end 初始为 0。一旦我们跨过了 end，我们就更新 jump，同时 end 的新值就是当前的 bound。这样当我们计算完倒数第 2 个位置后，便可返回 jump 值（因为倒数第 2 个位置以及之前，必然至少有一个位置能够跳跃到最后一个位置，否则我们就无法到达该位置 了，与题设不服）。
时间复杂度：O(n)
空间复杂度：O(1)

实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int jump(int[] nums) {
        int len = nums.length;
        int jump = 0;
        int bound = 0;
        int end = 0;
        for (int i = 0; i < len - 1; i++) {
                        
            bound = Integer.max(bound, i + nums[i]);
            
            if (i == end) {
                end = bound;
                jump++;
            }
        }
        return jump;
    }
}