题目描述：
给你一个非负整数数组 nums ，你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个下标，如果可以，返回 true ；否则，返回 false 。
数据范围：
$1\le nums.len \le 10^4, 0\le nums[i] \le 10^5$
题解：
假设当前为 $nums[i]$，下一步可以跳到 $[i, i + nums[i]]$，再下一次可以跳到区间右端点更远。可以依次遍历数组中的每一个元素，同时维护当前最远能到跳到的位置，如果这个位置到达了 $n - 1$ 就返回 $true$；如果当前位置 $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
24
25
26
27
28
| auto optimize_cpp_stdio = []()
{
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
return 0;
}();
class Solution
{
public:
const static int maxn = 1e4 + 10;
const static int maxm = 1e5 + 10;
const int INF = 0x3f3f3f3f;
bool canJump(vector<int> &nums)
{
int maxx = 0;
int n = nums.size();
for (int i = 0; i < n; ++i)
{
if(i > maxx)
return false;
maxx = max(maxx, i + nums[i]);
if(maxx >= n - 1)
return true;
}
return true;
}
};
|