题目描述
为了给刷题的同学一些奖励,力扣团队引入了一个弹簧游戏机。游戏机由 N
个特殊弹簧排成一排,编号为 0
到 N-1
。初始有一个小球在编号 0
的弹簧处。若小球在编号为 i
的弹簧处,通过按动弹簧,可以选择把小球向右弹射 jump[i]
的距离,或者向左弹射到任意左侧弹簧的位置。也就是说,在编号为 i
弹簧处按动弹簧,小球可以弹向 0
到 i-1
中任意弹簧或者 i+jump[i]
的弹簧(若 i+jump[i]>=N
,则表示小球弹出了机器)。小球位于编号 0
处的弹簧时不能再向左弹。
为了获得奖励,你需要将小球弹出机器。请求出最少需要按动多少次弹簧,可以将小球从编号 0
弹簧弹出整个机器,即向右越过编号 N-1
的弹簧。
样例
输入:jump = [2, 5, 1, 1, 1, 1]
输出:3
解释:小 Z 最少需要按动 3 次弹簧,小球依次到达的顺序为 0 -> 2 -> 1 -> 6,最终小球弹出了机器。
限制
1 <= jump.length <= 10^6
1 <= jump[i] <= 10000
算法1
(宽度优先遍历) $O(n)$
- 按照最朴素的想法,直接运用宽度优先遍历,找到从 $0$ 开始的最短路径。
- 但朴素的算法会超时,这是因为每个点连接的边数很多,达到了 $O(n)$ 的级别,直接暴力的时间复杂度为 $O(n^2)$。
- 仔细思考,发现除了 $i$ 可以到达 $i + jump(i)$ 之外,剩下从 $1$ 到 $i-1$ 的点,只需要遍历之前没有到过的地方,且一次遍历就可以覆盖一段区间。
- 所以,我们设置一个开始遍历的下限 $mi$,每次从 $mi$ 开始遍历到当前点 $u-1$,尝试进行转移。(如果 $mi \ge u$ 则直接不会进行枚举转移。)最后用 $u+1$ 更新 $mi$ 的最大值。
时间复杂度
- $i + jump(i)$ 的转移最多有 $O(n)$ 次,枚举的转移均摊下来总共也就 $O(n)$ 次,故总的时间复杂度为 $O(n)$。
空间复杂度
- 需要 $O(n)$ 的额外空间存储队列和距离数组。
C++ 代码
class Solution {
public:
int minJump(vector<int>& jump) {
const int n = jump.size();
queue<int> q;
vector<int> dis(n, INT_MAX);
dis[0] = 0;
q.push(0);
int mi = 1;
while (!q.empty()) {
int u = q.front();
q.pop();
if (u + jump[u] >= n)
return dis[u] + 1;
if (dis[u + jump[u]] > dis[u] + 1) {
dis[u + jump[u]] = dis[u] + 1;
q.push(u + jump[u]);
}
for (int i = mi; i < u; i++)
if (dis[i] > dis[u] + 1) {
dis[i] = dis[u] + 1;
q.push(i);
}
if (mi < u + 1)
mi = u + 1;
}
return n;
}
};
算法2
(等价构造,01 最短路) $O(n)$
- 这里介绍一种构图技巧,将 $O(n^2)$ 的边数降到 $O(n)$。
- $i$ 到 $i + jump(i)$ 连边,权值为 1。
- $i$ 到 $i’$ 连边,权值为 1。
- $i’$ 到 $i’-1$ 连边,权值为 0。
- $i’$ 到 $i$ 连边,权值为 0。
- 按照以上规则使用双端队列宽搜跑 01 最短路,点数和边数为 $O(n)$。
- 这种算法虽然麻烦,但作为一种思想更加通用,可以处理任意连接任意前缀的情况,甚至在树上处理连接任意子树的情况。
时间复杂度
- 点数和边数为 $O(n)$ 的 01 最短路的时间复杂度为 $O(n)$。
空间复杂度
- 需要 $O(n)$ 的额外空间存储队列和距离数组。
C++ 代码
class Solution {
public:
int minJump(vector<int>& jump) {
const int n = jump.size();
deque<int> q;
vector<int> dis(n * 2, INT_MAX);
dis[0] = dis[n] = 0;
q.push_back(0);
while (!q.empty()) {
int u = q.front();
q.pop_front();
if (u < n) {
if (u + jump[u] >= n)
return dis[u] + 1;
if (dis[u + jump[u]] > dis[u] + 1) {
dis[u + jump[u]] = dis[u] + 1;
q.push_back(u + jump[u]);
}
if (dis[u + n] > dis[u] + 1) {
dis[u + n] = dis[u] + 1;
q.push_back(u + n);
}
} else {
if (u - 1 >= n && dis[u - 1] > dis[u]) {
dis[u - 1] = dis[u];
q.push_front(u - 1);
}
if (dis[u - n] > dis[u]) {
dis[u - n] = dis[u];
q.push_front(u - n);
}
}
}
return n;
}
};