leetcode:45. 跳跃游戏II

45. 跳跃游戏 II

来源：力扣（LeetCode）

链接: https://leetcode.cn/problems/jump-game-ii

给你一个非负整数数组 nums ，你最初位于数组的第一个位置。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

你的目标是使用最少的跳跃次数到达数组的最后一个位置。

假设你总是可以到达数组的最后一个位置。

示例 1:

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

示例 2:

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

提示:

• $1<=nums.length<=10^4$
• $0<=nums[i]<=1000$

解法

• 贪心算法：从第一步起跳，然后找涵盖范围内能跳得最远的，然后之后以最远的那个为起点，开始找后续能跳得远的。
  

代码实现

贪心算法

• 原始实现

python实现

class Solution:
    def jump(self, nums: List[int]) -> int:
        if len(nums) <= 1:
            return 0
        
        start = 0
        end = 0  # 边界下标
        step = 0
        while end < len(nums)-1:
            maxpos = 0
            for i in range(start, end+1):
                maxpos = max(maxpos, i+nums[i])
            start = end  # 下一条的起点
            end = maxpos  # 最远的边界
            step += 1
        return step

c++实现

class Solution {
    
public:
    int jump(vector<int>& nums) {
    
        if (nums.size() <= 1) return 0;
        
        int start = 0, end = 0;
        int step = 0;
        while (end < nums.size()-1) {
    
            int maxpos = 0;
            for (int i=start; i <= end; i++) {
    
                maxpos = max(maxpos, i+nums[i]);
            }
            start = end;
            end = maxpos;
            step++;
        }
        return step;
    }
};

复杂度分析

• 时间复杂度： $O(N^2)$
• 空间复杂度： $O(1)$

• 优化

从上面代码观察发现，其实被 while 包含的 for 循环中，i 是从头跑到尾的。
只需要在一次 跳跃 完成时，更新下一次 能跳到最远的距离。
并以此刻作为时机来更新 跳跃 次数。
就可以在一次 for 循环中处理。

python实现

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

c++实现

class Solution {
    
public:
    int jump(vector<int>& nums) {
    
        if (nums.size() <= 1) return 0;

        int end = 0;
        int maxPostion = 0;
        int step = 0;
        for (int i=0; i<nums.size()-1; i++) {
    
            maxPostion = max(maxPostion, i+nums[i]);
            if (i == end) {
    
                end = maxPostion;
                step++;
            }
        }
        return step;
    }
};

复杂度分析

• 时间复杂度： $O(N)$
• 空间复杂度： $O(1)$

参考

• https://leetcode.cn/problems/jump-game-ii/solution/45-by-ikaruga/