【Leetcode 热题 100】45. 跳跃游戏 II

问题背景

给定一个长度为 $n$ 的 $0$ 索引 整数数组 $nums$。初始位置为 $nums[0]$。
每个元素 $nums[i]$ 表示从索引 $i$ 向前跳转的最大长度。换句话说，如果你在 $nums[i]$ 处，你可以跳转到任意 $nums[i+j]$ 处：

• $0\le j\le nums[i]$
• $i+j<n$
  返回到达 $nums[n-1]$ 的最小跳跃次数。生成的测试用例可以到达 $nums[n-1]$。

数据约束

• $1\le nums.length\le 10^4$
• $0\le nums[i]\le 1000$
• 题目保证可以到达$nums[n-1]$

解题过程

之前每日一题已经做过了，具体可以参考 每日一题的题解，再写一遍加强记忆。

具体实现

class Solution {public int jump(int[] nums) {int res = 0;int curEnd = 0;int nextEnd = 0;// 由于到达的位置是 n - 1，那么在 n - 2 的位置上有可能进行最后一次操作for(int i = 0; i < nums.length - 1; i++) {// 在每个位置上更新能够到达的最远边界nextEnd = Math.max(nextEnd, i + nums[i]);// 如果当前已经不能继续往前走，那么在这个位置上造桥if(i == curEnd) {curEnd = nextEnd;res++;}}return res;}
}