思路分析
一眼看上去就是个裸的BFS，但是写出来交一发直接TLE。考虑到复杂度本质上还是线性的，应该是由于一些内存开销导致时间超时。也就是说，这题存在某种常数优化，肯定是取决于一些具体的情况。仔细思考整个BFS过程，我们会发现，每一层BFS出来所能够到达的范围，在内存空间中完全是连续的。也就是说，我们只需要维护一次BFS以后的起始位置，以及所能够到达的最远位置即可。
为了得到最远位置，每一步我们可以一直遍历到上一次BFS所能够抵达的最远范围，然后记录一下新的最远可达范围即可。这样，就相当于每一步我们都走出了最优的解法：在当前的可达位置里面，选择了一步可以尽量跳得远的。这样，每一步相当于我们都走了尽量远的距离，直到最后我们的最远可达范围大于了n-1，说明已经可以走到终点了。
代码
class Solution {
public:
int jump(int A[], int n) {
if ( n <= 1 ) return 0;
int curSteps = 1;
int head = 0, far = A[head];
while ( head < far ) {
if ( far >= n - 1 ) return curSteps;
int target = far;
while ( head <= target ) {
far = max(far, head + A[head]);
head++;
}
head--;
curSteps++;
}
return -1;
}
};