55. Jump Game

You are given an integer array nums. You are initially positioned at the array's first index, and each element in the array represents your maximum jump length at that position.

Return true if you can reach the last index, or false otherwise.

Example 1:

1
2
3
Input: nums = [2,3,1,1,4]
Output: true
Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.

Example 2:

1
2
3
Input: nums = [3,2,1,0,4]
Output: false
Explanation: You will always arrive at index 3 no matter what. Its maximum jump length is 0, which makes it impossible to reach the last index.

题目大意

给定一个整数数组 nums，初始位置在数组的第一个索引（索引 0）。数组中的每个元素表示在该位置可以跳跃的最大长度。判断是否能够到达最后一个索引（数组的最后一个位置），返回 true 或 false。

例如：

  • 输入 nums = [2,3,1,1,4]，输出 true（从索引 0 跳 1 步到索引 1，再跳 3 步到最后索引）；
  • 输入 nums = [3,2,1,0,4]，输出 false（无论如何都会到达索引 3，但其最大跳跃长度为 0，无法到达最后索引）。

解题思路

核心思路是贪心算法，通过跟踪 “当前可到达的最远位置”，判断是否能覆盖到最后一个索引：

  1. 贪心策略：
    遍历数组时，实时更新从当前位置及之前所有位置能到达的最远索引（max_reach）。若在遍历过程中，max_reach 已覆盖最后一个索引，则直接返回 true；若遍历到某个位置时，该位置超出了 max_reach（即无法到达该位置），则返回 false。
  2. 关键逻辑：
    • max_reach 表示当前能到达的最远索引，初始值为 0；
    • 对于每个位置 i，更新 max_reach = max(max_reach, i + nums[i])（从位置 i 能跳到的最远位置）；
    • 若 max_reach >= n-1（n 为数组长度），说明已能到达最后一个索引，返回 true；
    • 若 i > max_reach，说明当前位置 i 无法到达，后续位置更无法到达，返回 false。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    bool canJump(vector<int>& nums) {
        int n = nums.size();
        int max_reach = 0;  // 当前能到达的最远索引
        
        for (int i = 0; i < n; ++i) {
            // 若当前位置超出可到达范围，无法继续前进
            if (i > max_reach) {
                return false;
            }
            // 更新最远可到达索引
            max_reach = max(max_reach, i + nums[i]);
            // 若已能到达最后一个索引，直接返回true
            if (max_reach >= n - 1) {
                return true;
            }
        }
        
        // 遍历结束后仍未到达最后一个索引
        return false;
    }
};