题目链接
题目描述
给定一个长度为
n
的
0
索引整数数组
nums
。初始位置为
nums[0]
。
每个元素
nums[i]
表示从索引
i
向前跳转的最大长度。换句话说，如果你在
nums[i]
处，你可以跳转到任意
nums[i + j]
处:
-
0<
=
j
<
=
n
u
m
s
[
i
]
0 <= j <= nums[i]
0
<=
j
<=
n
u
m
s
[
i
]
-
i+
j
<
n
i + j < n
i
+
j
<
n
返回到达
nums[n - 1]
的最小跳跃次数。生成的测试用例可以到达
nums[n - 1]
。
示例 1:
输入: nums = [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2。
从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。
示例 2:
输入: nums = [2,3,0,1,4]
输出: 2
提示：
-
1<
=
n
u
m
s
.
l
e
n
g
t
h
<
=
1
0
4
1 <= nums.length <= 10^4
1
<=
n
u
m
s
.
l
e
n
g
t
h
<=
1
0
4
-
0<
=
n
u
m
s
[
i
]
<
=
1000
0 <= nums[i] <= 1000
0
<=
n
u
m
s
[
i
]
<=
1000
-
题目保证可以到达
nums[n-1]
解法：贪心
用
c
u
r
cur
c
u
r
表示当前选择的跳跃位置的终点。
用
n
x
t
nxt
n
x
t
表示下一个跳跃位置的终点。
如果当前位置
i
=
c
u
r
i = cur
i
=
c
u
r
就表示，当前的
一跳
已经到达终点，所以要选择
下一跳
了。答案
a
n
s
+
=
1
ans += 1
an
s
+
=
1
，
c
u
r
cur
c
u
r
更新为
n
x
t
nxt
n
x
t
。
时间复杂度：
O
(
n
)
O(n)
O
(
n
)
C++代码：
class Solution {
public:
int jump(vector<int>& nums) {
int n = nums.size();
int ans = 0;
int cur = 0 , nxt = 0;
for(int i = 0;i < n;i++){
//nxt 更新为能到达的最远位置
nxt = max(nxt,i + nums[i]);
//i == cur 时，说明 当前跳 的距离已经用光了 ，需要选择 下一跳 了
// i ！= n -1 是因为我们要记录的是 跳数 不是跳的过程中经过的结点数，所以当 i==cur 并且 i 是最后一个
//位置时，我们不做处理
if(i == cur && i != n - 1){
ans++;
cur = nxt;
}
}
return ans;
}
};