Use PriorityQueue, O(n*lg(B)) (???)


  • 0
    T

    Let next[i] be the index of the optimal step from A[i]. We find next[i] backwards - that is to scan from A[n-1] to A[0].

    Use PriorityQueue<int[2]> pq to keep the cheapest total steps found so far (from A[i+1] to A[i+B], technically, pq could hold element from index larger than i+B, but we will discard them before peek the min value). Each element x in pq is int[2] type - x[1] is the index in A; x[0] is the optimal total steps from A[x[1]] to A[n-1].

    A few notes:

    1. if pq is emtpy, we can safely terminate the process;
    2. the runtime looks like O(n*lg(B)) to me, but I'm not 100% sure.
        public List<Integer> cheapestJump1(int[] A, int B) {
            int n = A.length;
            int[] next = new int[n];
    
            PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> (a[0] == b[0] ? a[1] - b[1] : a[0] - b[0]));
    
            List<Integer> ans = new ArrayList<>();
            pq.add(new int[]{0, n - 1 + B});
            for (int i = n - 1; i >= 0; i--) {
                if (A[i] == -1) continue;
                while (pq.size() > 0 && pq.peek()[1] > i + B)
                    pq.poll();
                if (pq.size() == 0) return ans;
                int[] min = pq.peek();
                pq.add(new int[]{A[i] + min[0], i});
                next[i] = min[1];
            }
    
            int i = 0;
            do {
                ans.add(i + 1);
                i = next[i];
            } while (i != n - 1 + B);
    
            return ans;
        }
    

Log in to reply
 

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