C++ O(n) time

• Basic idea is to use a window (implemented with `deque`) to maintain the candidate points of next jump

Each points will be only pushed into deque for once and there is no comparison in determine next stop.

However, I hate people when they say "lexicographically". This evil word ruin my morning.

``` static const int MAXN = 1010; class Solution { public: vector<int> cheapestJump(vector<int>& A, int B) { int next_stop[MAXN]; int payment[MAXN]; int i = A.size() - 1; deque <int> dq; next_stop[i] = 0; payment[i] = A[i]; //int start = 0; vector <int > ret; if (A[i] == -1){return ret;} dq.push_back(i); while(i >= 0){ if( A[i] != -1 ){ while (!dq.empty() && dq.back() > i + B ){ dq.pop_back(); } if (!dq.empty()){ next_stop[i] = dq.back(); payment[i] = payment[next_stop[i]] + A[i]; if (A[i] == 0 ){ dq.clear(); // dump all } while (!dq.empty() && payment[i] <= payment[dq.front()] ){ dq.pop_front(); } dq.push_front(i); }else{ return ret; } } i--; } i = 0; while(i != A.size() - 1){ ret.push_back(i + 1); i = next_stop[i]; } ret.push_back(A.size() ); return ret; } ```

```}; ```

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.