题目
2. 分析
很久没有写贪心的题了,在这题上卡了很久时间,我这个还是不会贪心。
核心思想就一句话:维护在到达本次最远位置之前能达到的最远位置。每到边界时就更新步数,便得到正确答案。
3. 代码
class Solution:
def jump(self, nums: List[int]) -> int:
max_pos, end, step = 0,0,0
for i in range(len(nums)-1):
# 算 max_pos 以内的点的最大值
if i <= max_pos:
max_pos = max(max_pos, nums[i] + i)
if i == end: # 说明到了边界点
end = max_pos # 更新下一次边界点
step+=1
return step
本站资源均来自互联网,仅供研究学习,禁止违法使用和商用,产生法律纠纷本站概不负责!如果侵犯了您的权益请与我们联系!
转载请注明出处: 免费源码网-免费的源码资源网站 » 【LeetCode】45.跳跃游戏II
发表评论 取消回复