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

【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 List

class Solution:
    def jump(self, nums: List[int]) -> int:
        ans = nowMax = nextMax = 0
        for i, l in enumerate(nums[:-1]):
            nextMax = max(nextMax, i + l)
            if i == nowMax:
                nowMax = nextMax
                ans += 1
        return ans

if __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 main

func jump(nums []int) (ans int) {
    var nowMax, nextMax int
    for i, l := range nums[:len(nums) - 1] {
        nextMax = max(nextMax, i + l)
        if nowMax == i {
            nowMax = nextMax
            ans++
        }
    }
    return
}

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

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