C++ O(n) time


  • 1
    S

    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;
    }
    

    };


Log in to reply
 

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