【每日算法Day 87】跳跃游戏II
Wallace Xu 2020-08-26 贪心
# LeetCode 45. 跳跃游戏 II (opens new window)
# 题目描述
给定一个非负整数数组，你最初位于数组的第一个位置。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
你的目标是使用最少的跳跃次数到达数组的最后一个位置。假设你总是可以到达数组的最后一个位置。
# 示例
输入: [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2。
从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。
1
2
3
4
2
3
4
# 解题思路
在每一次准备跳跃时我们维护当前能到达的最远位置farthest，记为边界。从左向右遍历数组，当到达边界时就更新下一跳能跳到的最远位置，并将跳数+1。
遍历数组时，不访问最后一个元素，因为在访问到最后一个元素之前，边界必然已经大于等于最后1个位置。如果访问最后一个元素并且恰巧边界就在最后一个位置，会增加一次不必要的跳跃次数。
public int jump(int[] nums) {
int n = nums.length;
int end = 0, farthest = 0, steps = 0;
for (int i = 0; i < n - 1; i++) {
//更新一跳中所有位置下一步能到达的最远位置
farthest = Math.max(farthest, nums[i] + i);
//如果到了一跳的结尾就更新下一跳的结尾位置，并将跳数+1
if (i == end) {
steps++;
end = farthest;
}
}
return steps;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
2
3
4
5
6
7
8
9
10
11
12
13
14