【LetMeFly】45.跳跃游戏 II：贪心（柳暗花明又一村）

力扣题目链接：https://leetcode.cn/problems/jump-game-ii/

给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。

每个元素 nums[i] 表示从索引 i 向前跳转的最大长度。换句话说，如果你在 nums[i] 处，你可以跳转到任意 nums[i + j] 处:

• 0 <= j <= nums[i] 
• i + j < n

返回到达 nums[n - 1] 的最小跳跃次数。生成的测试用例可以到达 nums[n - 1]。

 

示例 1:

输入: nums = [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2。从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。

示例 2:

输入: nums = [2,3,0,1,4]
输出: 2

 

提示:

• 1 <= nums.length <= 104
• 0 <= nums[i] <= 1000
• 题目保证可以到达 nums[n-1]

解题思路

假设第一步从0可以跳到1, 2, 3这3个位置，那么第二步从这三个位置中的哪一个开始起跳？

当然是从哪个能跳更远，就从哪个开始跳。

然后问题就解决了。

解题方法：贪心

使用一个变量记录上一步能跳到的最远位置$nowMax$，使用另一个变量记录这一步能跳到的最远位置$nextMax$。

遍历jump数组，并不断更新“这一步能跳到的最远位置”。

如果当前下标和“上一步能跳到的最远位置相同”（例如第一步可以跳到1, 2, 3，现在遍历到下标3了，待会儿是第二步才能到达的起点了），就：跳跃次数加一，更新$nowMax$为$nextMax$。

时空复杂度分析

• 时间复杂度$O(len(jump))
• 空间复杂度$O(1)$

AC代码

C++

/** @Author: LetMeFly* @Date: 2025-01-27 07:44:31* @LastEditors: LetMeFly.xyz* @LastEditTime: 2025-01-27 07:47:14*/
class Solution {
public:int jump(vector<int>& nums) {int ans = 0, nowMax = 0, nextMax = 0;for (int i = 0; i < nums.size() - 1; i++) {  // 注意这里的遍历范围nextMax = max(nextMax, i + nums[i]);if (nowMax == i) {ans++;  // 下一步还没跳，预先加了一步。所以已经跳到“目的位置前一个位置”就计算够了。nowMax = nextMax;}}return ans;}
};

Python

'''
Author: LetMeFly
Date: 2025-01-27 07:48:32
LastEditors: LetMeFly.xyz
LastEditTime: 2025-01-27 07:55:15
'''
from typing import Listclass Solution:def jump(self, nums: List[int]) -> int:ans = nowMax = nextMax = 0for i, l in enumerate(nums[:-1]):nextMax = max(nextMax, i + l)if i == nowMax:nowMax = nextMaxans += 1return ansif __name__ == '__main__':sol = Solution()ans = sol.jump([2, 3, 1, 1, 4])print(ans)assert ans == 2

Java

/** @Author: LetMeFly* @Date: 2025-01-27 07:55:47* @LastEditors: LetMeFly.xyz* @LastEditTime: 2025-01-27 07:56:59*/
class Solution {public int jump(int[] nums) {int ans = 0, nowMax = 0, nextMax = 0;for (int i = 0; i < nums.length - 1; i++) {nextMax = Math.max(nextMax, i + nums[i]);if (i == nowMax) {nowMax = nextMax;ans++;}}return ans;}
}

Go

/** @Author: LetMeFly* @Date: 2025-01-27 07:57:23* @LastEditors: LetMeFly.xyz* @LastEditTime: 2025-01-27 07:58:38*/
package mainfunc jump(nums []int) (ans int) {var nowMax, nextMax intfor i, l := range nums[:len(nums) - 1] {nextMax = max(nextMax, i + l)if nowMax == i {nowMax = nextMaxans++}}return
}

同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~

Tisfy：https://letmefly.blog.csdn.net/article/details/145374394