LeetCode 55. 跳跃游戏 | C++ 贪心算法最优解题解

📌 题目描述

题目级别：中等

给你一个非负整数数组 nums ，你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个下标，如果可以，返回 true ；否则，返回 false 。

• 示例 1:
  输入：nums = [2,3,1,1,4]
  输出：true
  解释：可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。

• 示例 2:
  输入：nums = [3,2,1,0,4]
  输出：false
  解释：无论怎样，总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 ， 所以永远不可能到达最后一个下标。

💡 解题思路：贪心算法 (范围覆盖视角)

遇到跳跃类的问题，很多人一开始会陷入误区：纠结于“我现在到底该跳 1 步、2 步还是 3 步？” 如果去穷举所有的跳法，时间复杂度会爆炸。

贪心算法的破局点在于：不要纠结具体的跳跃步数，而是看“覆盖范围”。

我们可以把问题转化为：只要我每次都尽力把“最远可达范围”向右扩展，最后看这个范围能不能覆盖到终点就行了。

核心运作机制：

1. 我们维护一个变量 r，代表当前能够到达的最远下标。初始时我们在下标 0，所以 r = 0。
2. 我们从左到右遍历数组中的每一个位置 i：
   • 前提条件：当前位置 i 必须在我们的可达范围之内（即 i <= r）。如果连位置 i 都走不到，那更别提从 i 往下跳了。
   • 贪心扩展：既然我能走到位置 i，那么我从位置 i 最远能跳到哪里呢？当然是 i + nums[i]。我们尝试用这个新距离去刷新我们的最远可达范围 r：r = max(r, i + nums[i])。
3. 遍历结束后（或者在遍历过程中），只要 r >= nums.size() - 1，就说明终点在我们的覆盖范围之内，返回 true。如果遍历完了发现 r 还是没能达到终点，说明半路卡死了，返回 false。

💻 C++ 代码实现

class Solution {
public:
    bool canJump(vector<int>& nums) {
        int r = 0; // 记录当前能够到达的最远下标
        int n = nums.size();
        
        // 遍历数组中的每一个位置
        for (int i = 0; i < n; i++) {
            // 只有当当前位置 i 能够被走到时，才有可能从这里继续起跳
            if (i <= r) {
                // 贪心策略：用当前位置能跳到的最远距离，去刷新全局的最远距离 r
                r = max(r, i + nums[i]);
            } else {
                // 优化剪枝：如果当前位置 i 已经超出了最远可达范围 r
                // 说明遇到了无法跨越的 "0"，后面永远走不到了，直接跳出
                break;
            }
        }

        // 最后判断最远可达范围是否覆盖了最后一个下标
        return r >= n - 1;
    }
};