贪心算法

跳跃游戏

中等#55Java时间 O(n)空间 O(1)

题目要做什么

从数组下标 0 出发,每个元素表示该位置最多能向右跳多少步。判断是否能到达最后一个位置。

题目示例输入nums = [2,3,1,1,4]
题目示例输出true

01 为什么这样做

维护当前能到达的最远位置 far。只有可达位置才能扩展 far;扫描遇到 i > far 时,当前位置和之后的位置都无法到达。

始终成立的条件

[0, far] 内的每个位置都可达;far 只会增加。

02 看见算法执行

动画与代码同步

修改输入,播放自己的例子

当前使用题目示例
修改输入会改变执行过程;预期输出用于核对结果。
数组 / nums步骤 1
执行状态
本次演示输出播放到最后查看

Solution.java参考解法
1class Solution {2    public boolean canJump(int[] nums) {3        int far = 0;4        for (int i = 0; i < nums.length; i++) {5            if (i > far) return false;6            far = Math.max(far, i + nums[i]);7        }8        return true;9    }10}

键盘控制:A 后退 · D 前进

编程练习

↑↓ 选择↵ 打开Pagefind 全文检索