0045. 跳跃游戏 II.md

0045. 跳跃游戏 II

• 标签：贪心、数组、动态规划
• 难度：中等

题目大意

给定一个非负整数数组 nums，数组中每个元素代表在该位置可以跳跃的最大长度。

开始位置为数组的第一个下标处，目的是用最少的跳跃次数到达最后一个下标处。

假设你总能到达数组的最后一个下标处。

解题思路

第 i 个位置所能跳到的位置为 [i + 1, i + nums[i]]，第 0 个位置所能跳到的位置就是 [0 + 1, 0 + nums[0]]，即 [1, nums[0]]，第 1 个位置所能跳到的位置就是 [1 + 1, 1 + nums[1]]，即 [2, 1 + nums[1]] ，等等。

对于每一个位置 i 来说，所能跳到的所有位置都可以作为下一个起跳点，为了尽可能使用最少的跳跃次数，所以我们应该使得下一次起跳所能达到的位置尽可能的远。简单来说，就是每次在「可跳范围」内选择可以使下一次跳的更远的位置。

在实现中，我们维护当前所能达到的最远位置 end，下一步所能跳到的最远位置 max_pos，最少跳跃次数 setps。

• 遍历 nums 的前 len(nums) - 1 个元素，更新 end 位置上下一步所能跳到的最远位置 max_pos。
  • max_pos 为 [i + 1, i + nums[i]] 范围内，所能跳到最远位置。
• 如果索引 i 到达了 end 边界，则：
  • 更新 end 为新的当前位置，并令步数 setps + 1。
• 最终返回跳跃次数 steps。

代码

class Solution:
    def jump(self, nums: List[int]) -> int:
        end, max_pos = 0, 0
        steps = 0
        for i in range(len(nums) - 1):
            max_pos = max(max_pos, nums[i] + i)
            if i == end:
                end = max_pos
                steps += 1
        return steps