LC55. 跳跃游戏

题目描述

给定一个非负整数数组 nums ，你最初位于数组的 第一个下标 。 数组中的每个元素代表你在该位置可以跳跃的最大长度。 判断你是否能够到达最后一个下标。

题目解析

题目在说什么

想象你站在一条长长的跳房子格子上，每个格子上面写着一个数字，比如 [2, 3, 1, 1, 4]。你一开始站在第 0 个格子（第一个格子）。每个格子上的数字代表：从这格出发，你最多能往前跳几步。比如格子上的数字是 2，那你就可以选择跳 1 步或 2 步，但不能跳 3 步。你的目标是：看看能不能跳到最后一个格子（也就是最后一个下标）。如果能，就返回 true，否则返回 false。

思路是怎么来的

这个问题很像“你在玩一个闯关游戏，每一关告诉你最多能往前冲多远”。我们最关心的是：我能不能一路冲到终点？而不是关心具体怎么跳（比如跳 1 步还是 2 步）。所以一个很自然的想法是：我每到一个格子，就看看从这格出发，最远能冲到哪个格子，然后把这个最远距离记下来。如果这个最远距离一直能覆盖到终点，那就说明可以到达。

举个例子：假设你站在第 0 格，上面写着 2，那最远能冲到第 2 格（0+2）。然后你走到第 1 格，上面写着 3，那最远能冲到第 4 格（1+3），这已经超过第 2 格了，所以你的最远距离更新为 4。接着你走到第 2 格，上面写着 1，最远只能到第 3 格，比 4 小，所以最远距离还是 4。然后走到第 3 格，上面写着 1，最远到第 4 格，还是 4。最后走到第 4 格，上面写着 4，最远到第 8 格，远超终点。所以你能到达终点。

这个思路的核心就是：不断更新你能到达的最远位置，只要这个最远位置能覆盖到你当前站的位置，你就还能继续往前走。如果某一步你发现最远位置已经够不到当前的位置了，那就说明你被困住了，到不了终点。

代码逐步拆解

我们来看参考代码，一行一行解释它在干什么。

int[] jump = new int[nums.length];

首先，我们创建一个数组 jump，长度和 nums 一样。这个数组用来记录：从每个格子出发，最远能跳到哪个下标。比如 nums[0] = 2，那么 jump[0] = 0 + 2 = 2，意思是从第 0 格出发，最远能跳到第 2 格。

for(int i = 0 ; i < nums.length ; i++){
    jump[i] = i + nums[i];
}

这个循环就是给 jump 数组赋值。对每个位置 i，最远能跳到的位置就是 i 加上它上面的数字 nums[i]。

int index = 0;
int maxJump = jump[0];

然后我们准备开始“走格子”。index 表示当前我们站在哪个格子，一开始站在第 0 格。maxJump 表示到目前为止，我们能到达的最远位置。一开始，从第 0 格出发，最远能到 jump[0]。

while(index < nums.length && index <= maxJump){

这个循环条件有两个：

• index < nums.length：我们还没走到格子外面去（还没走完所有格子）。
• index <= maxJump：当前站的位置 index 还在我们能到达的最远范围内。如果 index 超过了 maxJump，说明我们被困住了，无法再往前走。

    if(maxJump < jump[index]){
        maxJump = jump[index];
    }