【算法面试必刷】55. 跳跃游戏

目录

题目

题目链接

思路

复杂度

代码

题目

给你一个非负整数数组 nums ，你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个下标，如果可以，返回 true ；否则，返回 false 。

题目链接

55. 跳跃游戏 – 力扣（LeetCode）https://leetcode.cn/problems/jump-game/description/

思路

我们不需要关心具体怎么跳，只需要知道能跳到的最远位置 对于每个位置 i，它能到达的最远位置是 i + nums[i] 维护一个全局的最远可达位置 maxReach

复杂度

时间复杂度：O(n)

代码

class Solution {
public:
bool canJump(vector<int>& nums) {
int n = nums.size(); // 数组长度
int maxReach = 0; // 记录当前能到达的最远位置

// 遍历数组中的每个位置
for (int i = 0; i < n; i++) {
// 关键判断：如果当前位置已经超过了能到达的最远位置
// 说明无法到达当前位置，也就无法继续前进
if (i > maxReach) {
return false; // 无法到达终点，返回false
}

// 更新能到达的最远位置
// 从当前位置可以跳到 i + nums[i]，取最大值
maxReach = max(maxReach, i + nums[i]);

// 提前终止优化：如果已经能到达最后一个位置
// 直接返回true，不需要继续遍历
if (maxReach >= n – 1) {
return true;
}
}

// 遍历完整个数组都没有返回false，说明可以到达终点
return true;
}
};