Problem: 45. 跳跃游戏 II
文章目录
- 题目描述
- 思路
- 复杂度
- Code
题目描述
思路
Problem: 55.跳跃游戏
该题在上述的基础上,我们每次先求取当前可跳区间内的最远距离farthest;每当走到当前的区间胃部时(end == i):跳跃步数加一(jumps++),同时将下一次的可跳的最远区间更新(end = farthest;)
复杂度
时间复杂度:
O ( n ) O(n) O(n);其中 n n n为数组nums的大小
空间复杂度:
O ( 1 ) O(1) O(1)
Code
class Solution {
public:int jump(vector<int>& nums) {int n = nums.size();int end = 0;int farthest = 0;int jumps = 0;for (int i = 0; i < n - 1; ++i) {farthest = max(farthest, i + nums[i]);if (end == i) {jumps++;end = farthest;}}return jumps;}
};