- 标签:贪心、数组、动态规划
- 难度:中等
描述:给定一个非负整数数组 nums
,数组中每个元素代表在该位置可以跳跃的最大长度。开始位置位于数组的第一个下标处。
要求:判断是否能够到达最后一个下标。
说明:
-
$1 \le nums.length \le 3 \times 10^4$ 。 -
$0 \le nums[i] \le 10^5$ 。
示例:
- 示例 1:
输入:nums = [2,3,1,1,4]
输出:true
解释:可以先跳 1 步,从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。
- 示例 2:
输入:nums = [3,2,1,0,4]
输出:false
解释:无论怎样,总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 , 所以永远不可能到达最后一个下标。
如果我们能通过前面的某个位置
而前面的位置
- 初始化能到达的最远位置
$max_i$ 为$0$ 。 - 遍历数组
nums
。 - 如果能到达当前位置,即
$max_i \le i$ ,并且当前位置 + 当前位置最大跳跃长度 > 能到达的最远位置,即$i + nums[i] > max_i$ ,则更新能到达的最远位置$max_i$ 。 - 遍历完数组,最后比较能到达的最远位置
$max_i$ 和数组最远距离size - 1
的关系。如果$max_i >= len(nums)$ ,则返回True
,否则返回False
。
class Solution:
def canJump(self, nums: List[int]) -> bool:
size = len(nums)
max_i = 0
for i in range(size):
if max_i >= i and i + nums[i] > max_i:
max_i = i + nums[i]
return max_i >= size - 1
-
时间复杂度:$O(n)$,其中
$n$ 是数组nums
的长度。 - 空间复杂度:
按照位置进行阶段划分。
定义状态 dp[i]
表示为:从位置
- 如果能通过
$0 \sim i - 1$ 个位置到达$i$ ,即$dp[i-1] \le i$ ,则$dp[i] = max(dp[i-1], i + nums[i])$ 。 - 如果不能通过
$0 \sim i - 1$ 个位置到达$i$ ,即$dp[i - 1] < i$ ,则$dp[i] = dp[i - 1]$ 。
初始状态下,从 nums[0]
,即 dp[0] = nums[0]
。
根据我们之前定义的状态,dp[i]
表示为:从位置 dp[size - 1]
与数组最远距离 size - 1
的关系。
class Solution:
def canJump(self, nums: List[int]) -> bool:
size = len(nums)
dp = [0 for _ in range(size)]
dp[0] = nums[0]
for i in range(1, size):
if i <= dp[i - 1]:
dp[i] = max(dp[i - 1], i + nums[i])
else:
dp[i] = dp[i - 1]
return dp[size - 1] >= size - 1
-
时间复杂度:$O(n)$,其中
$n$ 是数组nums
的长度。 - 空间复杂度:$O(n)$。