55. Jump Game

by

55. Jump Game

Medium

Given an array of non-negative integers nums, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Determine if you are able to reach the last index.

Example 1:

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:

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.

Constraints:

  • 1 <= nums.length <= 3 * 104
  • 0 <= nums[i] <= 105

思路

从 start_index = 0 开始遍历，初始终点 farthest_end 为 index = 0 时能跳到的最远 index，即 nums[0]。

过程中每到新的一格，更新终点为 max(farthest_end, start_index + nums[start_index])。

当检测到 farthest_end >= size – 1 时，说明可以跳到最后一格，返回真。

当 start_index > farthest_end 退出循环时，说明无法跃过 farthest_end 值，返回假。

int max(int a, int b) {
    return a > b ? a : b;
}

class Solution {
public:
    bool canJump(vector<int>& nums) {
        int size = nums.size();
        if (size == 1) return true;
        
        int farthest_end = nums[0];
        for (int start_index = 0; start_index <= farthest_end; ++start_index) {
            farthest_end = max(farthest_end, start_index + nums[start_index]);
            if (farthest_end >= size - 1) return true;
        }
        return false;
    }
};

Runtime: 4 ms, faster than 99.41% of C++ online submissions for Jump Game.

Memory Usage: 12.8 MB, less than 85.74% of C++ online submissions for Jump Game.

Leave a Comment