题目描述
给定一个非负整数数组 nums
,你最初位于数组的第一个位置。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
你的目标是使用最少的跳跃次数到达数组的最后一个位置。
假设你总是可以到达数组的最后一个位置。
样例
输入:nums = [2,3,1,1,4]
输出:2
解释:跳到最后一个位置的最小跳跃数是 2。
从下标为 0 跳到下标为 1 的位置,跳 1 步,然后跳 3 步到达数组的最后一个位置。
输入:nums = [2,3,0,1,4]
输出:2
限制
1 <= nums.length <= 10^4
0 <= nums[i] <= 1000
算法1
(动态规划,贪心) O(n)
- 设状态 f(i) 表示到达 i 所需要的最少步数。
- f(0)=0,其余待定。定义辅助指针 last 为第一次到达 i 时上一步的位置,last 从 0 开始。
- 通过归纳可以得知,从小到大遍历过程中,第一次通过 x 可以到达 y 时,y 的最少步数就是 x 的最少步数加 1。因为一次移动,可以从 x 到 [x+1,x+nums(x)] 的任意位置,所以根据归纳(即 x 也是这样到达的),这样一定是最优的。
- 根据以上得知,令 f(i)=f(last)+1 后,f(i) 就会是最优值。
- 故可以根据 i 来让 last 向后移动,找到最早的可以一步到达 i 的位置,然后根据 f(last) 更新 f(i)。
时间复杂度
- 数组的每个元素最多被遍历两次,故时间复杂度为 O(n)。
空间复杂度
- 需要 O(n) 的额外空间存储状态。
C++ 代码
class Solution {
public:
int jump(vector<int>& nums) {
const int n = nums.size();
vector<int> f(n);
f[0] = 0;
int last = 0;
for (int i = 1; i < n; i++) {
// 依次求 f[i] 的值。
while (i > last + nums[last]) // 根据 i 来更新 last。
last++;
f[i] = f[last] + 1; // 根据 f[last] 更新 f[i]。
}
return f[n - 1];
}
};
算法2
(贪心,双指针) O(n)
- 定义指针 cur 和 dis,分别表示当前位置和可达到的最远位置。定义一轮遍历过程如下:
- 移动 cur 到 dis,途中记录可以达到的最远位置 next。
- 答案加 1。
- 更新 dis 为 next。
- 当 dis 大于等于 n−1 时视为到达,返回答案。
时间复杂度
- 数组的每个元素最多被遍历两次,故时间复杂度为 O(n)。
空间复杂度
- 仅需要常数的额外空间。
C++ 代码
class Solution {
public:
int jump(vector<int>& nums) {
const int n = nums.size();
int ans = 0, cur = 0, dis = 0;
while (dis < n - 1) {
int next = 0;
while (cur <= dis) {
next = max(next, cur + nums[cur]);
cur++;
}
ans++;
dis = next;
}
return ans;
}
};
感觉这题严格来说,不像是贪心,而是BFS找最短路径。
膜拜
可以说说 i > last + nums[last] 的含义吗
找到最小的可以一步到达 i 的位置
膜拜大佬
/* f[i]代表nums[i]到nums[0]的最短距离 f[i]是分段的,每隔一段就加1。idx就代表每段最后一个位置,idxNext代表下一段最后一个位置 根据当前分段的最远距离,不断更新idxNext */ class Solution { public: int jump(vector<int>& nums) { if (nums.empty()) return 0; // idx代表这次最远序号, idxNext代表下一个最远序号, f代表nums[i]到nums[0]的最短距离 int len = nums.size(), idx = 0, idxNext = 0, f = 0; for (int i = 0; i < len; i ++) { if (idx == i-1) { //过了上个分段,本段f加1 f ++; idx = idxNext; //先更新idx } idxNext = max(idxNext, i + nums[i]); //后更新idxNext } return f; } };
在leetcode 看题解 有人写道参考wzc1995 得知单调性云云。
马上切回acwing看题解了.点赞,学习
不是很理解 last 一定是随着 i 递增的这里
如果有小于 last 的点可以到达 i,会产生矛盾
假设 last′<last 且也可以到达 i,可以考虑在什么情况下会放弃 last′ 的位置继续向后移动呢?根据算法定义,一定存在某个点 j,满足 j>last′+num(last′),而 i>j,所以 i>last′+num(last′),即 last′ 一定无法到达 i,矛盾。
请问大佬,这里为何有 i > j ,不是很理解
超清晰!
请问这个题是
dijkstra算法
的变形吗?如果用最短路模型时间复杂度必然会到 n2,所以和最短路算法无关
这可以算是个双指针模型。
请问为什么可以使用贪心来解?即为什么
最早得可以一步到达i的位置
可以构成最小的步数?感谢回答!这里的核心思想是动态规划,即
f[i]
表示到达i
的最少步数。转移时,可以利用贪心来优化,免除了循环n
来寻找可以转移到位置i
的最优决策。这里的贪心思想为,如果在某个位置last
可以一步到达i
,则last
之后的位置就都不必再枚举了,而且这个last
是随着i
单调递增的,所以我们在动态规划的过程中,维护last
变量。清晰明了!
还想问一下,
f[i] = f[last]
发生时,i一定是由last位置跳过去的吗?是的