JAVA练习351- 跳跃游戏

题目概览给你一个非负整数数组nums你最初位于数组的第一个下标。数组中的每个元素代表你在该位置可以跳跃的最大长度。判断你是否能够到达最后一个下标如果可以返回true否则返回false。示例 1输入nums [2,3,1,1,4]输出true解释可以先跳 1 步从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。示例 2输入nums [3,2,1,0,4]输出false解释无论怎样总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 所以永远不可能到达最后一个下标。提示1 nums.length 10^40 nums[i] 10^5来源55. 跳跃游戏 - 力扣LeetCode解题分析方法动态规划令当前索引为 i当前索引是否可达得看 [ 0, i) 的跳跃距离令其中某个索引为 j即 num[ j ] j 是否大于等于 i如果 nums[ j ] j 是最大跳跃距离那么其他距离我们也不用关心了。可以得到转移方程dp[ i ] max { num[0] 0, nums[1] 1, ... nums[ i - 1 ] i - 1 } i因此我们可以定义一个变量 maxDepth 存储 [ 0, i ) 之间的最大跳跃距离如果 maxDepth i说明跳不到返回 false否则比较 num[ i ] i 与 maxDepth 的大小更新 maxDepth。时间复杂度O(n)空间复杂度O(1)class Solution { public boolean canJump(int[] nums) { int n nums.length; int maxDepth 0; for (int i 0; i n; i) { if (i maxDepth) { return false; } maxDepth Math.max(maxDepth, nums[i] i); } return true; } }