Medium

题目描述

给定一个长度为 n 的 0 索引整数数组 nums。你最初位于索引 0。

每个元素 nums[i] 表示从索引 i 向前跳跃的最大长度。换句话说，如果你在索引 i，你可以跳跃到任何索引 (i + j)，其中：

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

返回到达索引 n - 1 的最少跳跃次数。测试用例保证你可以到达索引 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 <= 10^4
  • 0 <= nums[i] <= 1000
  • 保证可以到达 nums[n - 1]

解题思路

这道题要求找到跳跃到最后一个位置的最少步数，有多种解法思路：

贪心算法（推荐）

核心思想是在每一步中尽可能跳到能够到达最远位置的点。我们维护当前跳跃能到达的最远边界，当到达边界时，必须进行下一次跳跃。

具体实现：

  • 用 currentEnd 记录当前跳跃次数下能到达的最远位置
  • 用 farthest 记录遍历过程中能到达的最远位置
  • 当 i == currentEnd 时，说明必须跳跃，更新边界并增加跳跃次数

动态规划

用 dp[i] 表示到达位置 i 的最少跳跃次数，对每个位置尝试所有可能的跳跃。时间复杂度较高，为 O(n²)。

BFS

将问题看作图的最短路径问题，每次跳跃看作一层遍历。虽然概念清晰，但实现相对复杂。

贪心算法在此问题中最优，既简洁又高效，时间复杂度为 O(n)。

代码实现

class Solution {
public:
    int jump(vector<int>& nums) {
        int n = nums.size();
        if (n <= 1) return 0;
        
        int jumps = 0;
        int currentEnd = 0;
        int farthest = 0;
        
        for (int i = 0; i < n - 1; i++) {
            farthest = max(farthest, i + nums[i]);
            
            if (i == currentEnd) {
                jumps++;
                currentEnd = farthest;
            }
        }
        
        return jumps;
    }
};

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

public class Solution {
    public int Jump(int[] nums) {
        int n = nums.Length;
        if (n <= 1) return 0;
        
        int jumps = 0;
        int currentEnd = 0;
        int farthest = 0;
        
        for (int i = 0; i < n - 1; i++) {
            farthest = Math.Max(farthest, i + nums[i]);
            
            if (i == currentEnd) {
                jumps++;
                currentEnd = farthest;
            }
        }
        
        return jumps;
    }
}

/**
 * @param {number[]} nums
 * @return {number}
 */
var jump = function(nums) {
    let jumps = 0;
    let currentEnd = 0;
    let farthest = 0;
    
    for (let i = 0; i < nums.length - 1; i++) {
        farthest = Math.max(farthest, i + nums[i]);
        
        if (i === currentEnd) {
            jumps++;
            currentEnd = farthest;
        }
    }
    
    return jumps;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型贪心算法动态规划
时间复杂度O(n)O(n²)
空间复杂度O(1)O(n)

相关题目