题目：给定一个非负整数数组，你最初位于数组的第一个位置。数组中的每个元素代表你在该位置可以跳跃的最大长度。判断你是否能够到达最后一个位置。
第一印象
第一个感觉是动态规划，觉得可以用当前位置所能达到的最远距离来判断，只要这个最远距离大于最后一个位置的坐标，那就一定可以到达，反之亦然。时间复杂度O（N），空间复杂度O（1）。
代码
public boolean canJump(int[] nums) {
int len = nums.length;
int max = nums[0];
for(int i = 0; i <= max; i ++) {
if(nums[i] + i > max)
max = nums[i] + i;
if(max >= len - 1)
return true;
}
return false;
}
代码相当简洁，结果跑出来时间复杂度和空间复杂度居然都不是最优的一档，我蓝步芦表示不服QAQ，一定是Java语言的问题！
打开官解，果然是我这种做法，不过这家贪心算法哈哈哈哈哈哈，手动尴尬(─.─|||
也对哦，毕竟没有用数组维护各个位置的状态，仅维持可达最远的距离。
就酱紫。
网友评论