企业官网建设流程全解析

题目：

解题：

运行结果：

解题思路：

一、读题

1、非负整数数组：里面数字 ≥ 0，可以是 0。0 的意思：站在这里一步都跳不动，卡死了。

2、初始位置：下标 0，也就是数组第一个元素那里。

3、nums[i] 的含义：站在下标 i 的时候，最多往前跳 nums [i] 步。

重点！！是【最多跳这么多】，不是必须跳这么多。举个例子：nums [i]=3，代表你可以跳 1 步、2 步、或者 3 步，随便选，但是不能跳 4 步。

4、目标：能不能抵达最后一个下标，不是要跳出数组！比如数组长度是 5，下标是 0,1,2,3,4，目标就是下标 4，只要能摸到下标 4 就成功。

看示例 1：nums = [2,3,1,1,4] 下标：0 1 2 3 4 值： 2 3 1 1 4

nums [0]=2：站 0 号位置，最多跳 2 步 → 能跳到下标 1，下标 2

nums [1]=3：站 1 号位置，最多跳 3 步 → 1+3=4，刚好是终点下标，所以成功，true

二、【回溯 】

那我是不是要把所有可能跳的路线全部试一遍？比如 nums=[2,3,1,1,4]

从 0 出发，可以跳到 1 或者跳到 2

分支 1：0→1，从 1 又可以跳到 2、3、4，看到 4，成功

分支 2：0→2，从 2 可以跳到 3，从 3 跳到 4，也成功

但是看到提示：nums 长度最多可以到 10⁴，也就是一万个元素。

所以我们换一个角度：到当前为止，我最远能覆盖到哪个下标？这就是贪心思路的起点。

定义一个变量：maxReach

含义：在遍历到现在，所有我们能到达的位置里面，最远能够跳到的下标。

核心规则：

1、只要一个下标 i ≤ maxReach → 下标 i 这个位置是我们可以抵达的；

2、如果 i > maxReach → i 这个位置我们根本到不了，后面所有位置都不用看了。

3、站在可以抵达的 i 点上，这个点能帮我们拓展新的最远边界：

新候选最远 = i + nums [i] 我们拿这个候选，和原来的 maxReach 比，谁大，谁就是新的 maxReach。

4、只要 maxReach ≥ 终点下标，直接成功。

贪心本质：每次走能走的地方，不断往外推最远边界，边界碰到终点就赢，边界追不上当前 i 就输。