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:

- if
`pq`

is emtpy, we can safely terminate the process; - 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;
}
```