leetcode hot100跳跃游戏Ⅱ

本题和上一题还是有不一样的地方，这个题中，我们需要记录我们跳跃的步数并尽可能的满足最小的跳跃步数到达终点。

那么我们还是采用覆盖范围的概念，但是我们需要两个，一个是在当前位置的覆盖范围，另一个是下一步的覆盖范围。

当我们位于当前位置，我们计算我们可以走到的最大覆盖范围，如果最大覆盖范围大于等于nums.length-1，也就是说我们在当前位置，再走一步，就可以到达数组的终点，那么此时直接步数加一，然后跳出循环即可。

如果我们当前位置，发现最大覆盖范围没有到达重点，那么我们应该继续往下走，往下走的时候，我们就需要计算，下一步无论是往后走几步，我们要找到下一步走完之后的最大覆盖范围，然后把这个值给当前的覆盖范围，然后步数加一，这样就说明，我们在步数加一的情况下，我们可以走到的最远距离！

本题和上一题不一样的点在于，上一个题我们只需要找最大的覆盖范围即可，所以我遍历的时候，是在覆盖范围内遍历，这个题是要找最小的步数，我们需要数组中每个元素都遍历，然后根据当前元素的值去改变最大覆盖范围，如果超过了数组的索引最大值，那么说明再走一步肯定能到最后（注意，可能不是从当前位置走的，可能是当前位置前一个位置，因为我们不关心走的路线，只关心最大范围！）。如果当前的最大范围和数组下标i相等了，说明我们当前走到的位置还到不了数组最后终点，还需要再往后走，然后我们往后走，那么最大覆盖范围肯定变化了，就把这个最大覆盖范围给当前覆盖范围，继续用i和当前覆盖范围比较！

class Solution {
    public int jump(int[] nums) {
        if (nums == null || nums.length == 0 || nums.length == 1) {
            return 0;
        }
        //记录跳跃的次数
        int count=0;
        //当前的覆盖最大区域
        int curDistance = 0;
        //最大的覆盖区域
        int maxDistance = 0;
        for (int i = 0; i < nums.length; i++) {
            //在可覆盖区域内更新最大的覆盖区域
            maxDistance = Math.max(maxDistance,i+nums[i]);
            //说明当前一步，再跳一步就到达了末尾
            if (maxDistance>=nums.length-1){
                count++;
                break;
            }
            //走到当前覆盖的最大区域时，更新下一步可达的最大区域
            if (i==curDistance){
                curDistance = maxDistance;
                count++;
            }
        }
        return count;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28