Greedy, Greedy, Greedy.. It is all about maximum interval update.
One trick is, we start looping over each element from the one nearest to end to farthest one - because the nearer the index is, more hopeful it could finish earlier. With this optimization, I got it passed with only 24ms.
class Solution { public: int jump(int A[], int n) { if (n <= 1) return 0; int last = 0, inx = 0; int cnt = 0; while (inx < n) { int newMaxInx = 0; int tmp_i = inx + 1; while (tmp_i--) { if (tmp_i < last) break; newMaxInx = std::max(newMaxInx, A[tmp_i] + tmp_i); if (newMaxInx >= n - 1) return cnt + 1; } last = inx; inx = newMaxInx; cnt++; } return cnt; } };
LeetCode "Jump Game II",布布扣,bubuko.com
原文：http://www.cnblogs.com/tonix/p/3884666.html