给定一个非负整数数组 nums ,你最初位于数组的 第一个下标 。 数组中的每个元素代表你在该位置可以跳跃的最大长度。 判断你是否能够到达最后一个下标。为什么要用i+nums[i]
时间: 2024-05-29 17:14:29 浏览: 96
python 实现给你一个整数数组 nums ,数组中的元素 互不相同 。返回该数组所有可能的子集(幂集)
5星 · 资源好评率100%
可以用贪心算法来解决这个问题。我们从左往右遍历数组,维护一个变量 `farthest` 表示从当前位置出发能够到达的最远位置。对于每个位置 `i`,如果 `farthest < i`,说明无法到达位置 `i`,直接返回 `false`。否则,我们更新 `farthest` 为 `max(farthest, i + nums[i])`,表示从位置 `i`出发能够到达的最远位置。如果 `farthest` 大于或等于数组的最后一个位置 `n-1`,则说明可以到达最后一个位置,返回 `true`。
为什么要用 `i + nums[i]` 来更新 `farthest` 呢?因为从位置 `i` 出发能够到达的最远位置是 `i + nums[i]`,我们需要更新 `farthest`,使其尽可能地大,以便能够到达更远的位置。
阅读全文