LeetCode 45 Jump Game II

题目链接:Jump Game II

题意:给一个数组 \(A\)\(A_i\) 表示在 \(i\) 位置时一步能前进的最长距离,现在从下标0开始前进,问最少多少步能到达终点

 

可以贪心解决

若当前位置下标为 \(k\) ,则跳到距离范围内 \(i+A_i(i\in (k,k+A_k])\) 最大的位置,也就是下一次能走最远的位置。

时间复杂度 \(O(n)\)

 

 

Categories: LeetCode