Условие: Дан целочисленный массив nums. Изначально вы находитесь в первом индексе массива, и каждый элемент массива представляет максимальную длину прыжка в этой позиции.
Верните true, если вы можете добраться до последнего индекса, или false в противном случае.
Пример:
Ввод: nums = [1,3,1,1,4]
Вывод: true
Объяснение: Переходим на 1 шаг от индекса 0 к 1, затем на 3 шага к последнему индексу.
Ввод: nums = [3,2,1,0,4]
Вывод: false
Решение:
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;
maxReach = max(maxReach, i + nums[i]);
}
return true;
}
};
Временное решение: O(N)Пространственное решение: O(1)