当前位置：首页 > article >正文

【Leetcode 每日一题】45. 跳跃游戏 II

article 2025/1/29 20:30:12

问题背景

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

$\le j \le nums[i]$
$\lt n$
返回到达 $n u m s [n - 1]$ 的最小跳跃次数。生成的测试用例可以到达 $n u m s [n - 1]$ 。

数据约束

● $\le nums.length \le 10 ^ 4$
● $\le nums[i] \le 1000$
● 题目保证可以到达 $n u m s [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;
    }
}