【Leetcode 热题 100】45. 跳跃游戏 II
问题背景
给定一个长度为 n n n 的 0 0 0 索引 整数数组 n u m s nums nums。初始位置为 n u m s [ 0 ] nums[0] nums[0]。
每个元素 n u m s [ i ] nums[i] nums[i] 表示从索引 i i i 向前跳转的最大长度。换句话说，如果你在 n u m s [ i ] nums[i] nums[i] 处，你可以跳转到任意 n u m s [ i + j ] nums[i + j] nums[i+j] 处：
- 0 ≤ j ≤ n u m s [ i ] 0 \le j \le nums[i] 0≤j≤nums[i]
- i + j < n i + j \lt n i+j<n
返回到达 n u m s [ n − 1 ] nums[n - 1] nums[n−1] 的最小跳跃次数。生成的测试用例可以到达 n u m s [ n − 1 ] nums[n - 1] nums[n−1]。
数据约束
- 1 ≤ n u m s . l e n g t h ≤ 1 0 4 1 \le nums.length \le 10 ^ 4 1≤nums.length≤104
- 0 ≤ n u m s [ i ] ≤ 1000 0 \le nums[i] \le 1000 0≤nums[i]≤1000
- 题目保证可以到达 n u m s [ n − 1 ] nums[n-1] 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;}
}