为了给刷题的同学一些奖励，力扣团队引入了一个弹簧游戏机。游戏机由 N 个特殊弹簧排成一排，编号为 0 到 N-1。初始有一个小球在编号 0 的弹簧处。若小球在编号为 i 的弹簧处，通过按动弹簧，可以选择把小球向右弹射 jump[i] 的距离，或者向左弹射到任意左侧弹簧的位置。也就是说，在编号为 i 弹簧处按动弹簧，小球可以弹向 0 到 i-1 中任意弹簧或者 i+jump[i] 的弹簧（若 i+jump[i]>=N ，则表示小球弹出了机器）。小球位于编号 0 处的弹簧时不能再向左弹。
为了获得奖励，你需要将小球弹出机器。请求出最少需要按动多少次弹簧，可以将小球从编号 0 弹簧弹出整个机器，即向右越过编号 N-1 的弹簧。
示例 1：
输入：jump = [2, 5, 1, 1, 1, 1]
输出：3
解释：小 Z 最少需要按动 3 次弹簧，小球依次到达的顺序为 0 -> 2 -> 1 -> 6，最终小球弹出了机器。
限制：
1 <= jump.length <= 10^6
1 <= jump[i] <= 10000
给定一个数组，每个数表示能从该位置往右跳的的步数。每个位置，要么往右一次性跳这么多步，要么可以跳回左边任意位置。问要跳出最右边，需要最少跳是多少。
每跳到一个i，可以往右跳到i+jump[i]，或者跳回[0,i-1]任意位置。采用BFS思路，i+jump[i]和[0,i-1]任意位置作为BFS的一层。但是，简单的BFS会TLE。每轮BFS时，记录[0,i-1]测试过的最大位置，下次只要从这个位置开始测试即可。
完整代码如下：
class Solution {
public:
int minJump(vector<int>& jump) {
int n = jump.size();
vector<int> visited(n, 0);
visited[0] = 1;
queue<int> q;
q.push(0);
int steps = 0;
int premax = 0;
while (!q.empty()) {
++steps;
int sz = q.size();
while (sz--) {
int cur = q.front();
q.pop();
int next = cur + jump[cur];
if (next >= n)return steps;
if (visited[next] == 0) {
q.push(next);
}
for (int pre = premax; pre < cur; ++pre) {
if (visited[pre] == 0) {
visited[pre] = 1;
q.push(pre);
}
}
premax = max(premax, cur);
}
}
return 0;
}
};本代码提交AC，用时544MS。