跳跃游戏
题目链接: https://leetcode.cn/problems/jump-game
解题思路:
正向遍历:从头开始遍历,用一个遍历记录我们能够跳到的最远距离,逐步更新最远距离,若能到达目标位置,即为成功
反向遍历:若一个点能到达目标节点,将其更新为目标节点,若最终目标节点为起点,说明可以从起点跳到终点
复杂度分析
时间复杂度: 只遍历了一遍数组 ,因此时间复杂度为 ,其中 是数组 的长度
空间复杂度: 只使用了常数个变量,因此空间复杂度为 ,无论输入的数组 的长度如何,函数使用的空间都是固定的
最后更新于