【Hot 100 刷题计划】 LeetCode 45. 跳跃游戏 II | C++ 贪心算法最优解题解

LeetCode 45. 跳跃游戏 II | C++ 动态规划与贪心 O(N) 双解法题解

📌 题目描述

题目级别：中等

给定一个长度为n的0 索引整数数组nums。初始位置在下标 0。
每个元素nums[i]表示从索引i向后跳转的最大长度。
返回到达n - 1的最小跳跃次数。测试用例保证可以到达n - 1。

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

💡 解题思路与代码实现

这道题求的是“最少步数”，很自然会让人想到动态规划（求极值）。但如果想要追求极致的性能，我们需要利用跳跃游戏的特殊性质，使用贪心算法进行降维打击。

🚀 解法一：动态规划 (思路直观，易于理解)

核心思想：
我们开辟一个dp数组，dp[i]表示到达索引i需要的最少跳跃次数。
初始状态dp[0] = 0，其余全部初始化为无穷大。
遍历数组，站在位置i时，我们把它能跳到的所有未来位置j都更新一遍：dp[j] = min(dp[j], dp[i] + 1)。

💻 C++ 代码实现

classSolution{public:intjump(vector<int>&nums){intn=nums.size();vector<int>dp(n,0x3f3f3f3f);// 初始化为无穷大dp[0]=0;// 起点不需要跳跃for(inti=0;i<n;i++){// 遍历从当前位置 i 能够跳到的所有位置 jfor(intj=i+1;j<=i+nums[i]&&j<n;j++){dp[j]=min(dp[j],dp[i]+1);}}returndp[n-1];}};

🏆 解法二：贪心算法 (时间 O(N)，大厂面试终极解)

既然是跳跃，我们其实不需要挨个更新后面的格子。我们可以把跳跃看作是一次次扩大势力范围的过程。

核心机制：

我们维护两个变量：farthestfarthestfarthest(当前接触过的所有点中，能跳到的最远距离) 和currentendcurrent_{end}currentend​(当前这一步所能覆盖的右边界)。

遍历数组，每经过一个格子iii，我们就尝试用它去刷新farthestfarthestfarthest。

灵魂转折点：当我们遍历到currentendcurrent_{end}currentend​时，说明“当前这一步的潜力已经全部榨干了”。为了继续往前走，我们被迫必须进行下一次跳跃。于是跳跃次数jumps++jumps++jumps++，并把下一步的边界currentendcurrent_{end}currentend​更新为刚才探索到的最远距离farthestfarthestfarthest。

💻 进阶 C++ 代码实现

classSolution{public:intjump(vector<int>&nums){intjumps=0;// 记录跳跃次数intcurrent_end=0;// 记录当前这一跳的最远边界intfarthest=0;// 记录在当前边界内，能探索到的全局最远距离// 注意：这里 i < nums.size() - 1，因为到了终点就不需要再跳了for(inti=0;i<nums.size()-1;i++){// 贪心：在前进的过程中，不断刷新能到达的最远距离farthest=max(farthest,i+nums[i]);// 如果走到了当前这一跳的边界if(i==current_end){jumps++;// 必须进行下一次跳跃current_end=farthest;// 更新下一跳的边界}}returnjumps;}};