LeetCode 补充题 125. 跳跃路径的最大得分
题目描述
[!green]
牛客原题： ✅ 补充题 125. 跳跃路径的最大得分
给你一个非负整数数组
nums，你从下标0出发，只能向右跳跃。nums[i]表示从下标i最多可以向右跳的步数。每到达一个位置，就获得该位置的数值作为积分，起点和终点也计分。只有到达最后一个位置才算成功。
返回成功到达终点时能够获得的最大积分。如果数组为空或终点不可达，返回
-1。
示例 1：
输入：
nums = [2,4,0,2,0,100]
输出：108
解释： 路径下标为 0→1→3→5，积分为 2+4+2+100=108，且每次跳跃都在允许范围内。
提示：
- 数组元素为非负整数，只能向右跳。
- 起点和终点的数值均计入积分。
- 空数组或终点不可达时返回
-1。
题意分析
到达位置
i的最优路径，一定来自某个仍能跳到i的前驱j。已知前驱最优积分后，转移就是在所有满足j < i <= j + nums[j]的位置中取最大积分，再加上nums[i]。前驱的覆盖终点各不相同，不能只记录一个全局最大分数。用最大堆按积分排列候选，同时保存它最远能到的下标，才能区分高分但已经失效的路径。
解法：最大堆维护尚可到达的最优前驱
核心思路
[!blue]
堆项保存前驱的最优积分
score和可覆盖的最右位置end。处理i前不断弹出end < i的堆顶；清理后若堆不空，堆顶就是所有有效前驱中积分最大的一个，因为任何更高分项都已先被检查。用堆顶积分加
nums[i]得到当前位置最优值，再将新候选加入堆。堆中较低分的过期项暂时不影响答案，可以等到成为堆顶时再删除，每项至多入堆和出堆一次。若堆空，所有此前可达位置都跳不到
i，也无法跳到更远的位置，因为允许的步长覆盖从 1 到最大步数的完整区间，因此可以直接返回 -1。单元素数组返回起点积分，最终答案只取终点状态。
解题步骤
- 将起点的积分与最远可达下标放入最大堆。
- 处理位置 i 时，不断删除堆顶中无法覆盖 i 的候选。
- 没有候选则终点不可达；否则由堆顶积分加当前位置值计算新状态并入堆。
- 返回到达最后位置的积分，不把中途死路的最高分当作答案。
代码实现
class Solution {
public long maxJumpScore(int[] nums) {
if (nums.length == 0) {
return -1;
}
PriorityQueue<long[]> heap = new PriorityQueue<>((a, b) -> Long.compare(b[0], a[0]));
heap.add(new long[] {
nums[0],
nums[0]
});
long score = nums[0];
for (int i = 1; i < nums.length; i++) {
while (!heap.isEmpty() && heap.peek()[1] < i) {
heap.poll();
}
if (heap.isEmpty()) {
return -1;
}
score = heap.peek()[0] + nums[i];
heap.add(new long[] {
score,
(long) i + nums[i]
});
}
return score;
}
}
import "container/heap"
type jumpEntry struct {
score int64
end int
}
type jumpHeap []jumpEntry
func (h jumpHeap) Len() int {
return len(h)
}
func (h jumpHeap) Less(i, j int) bool {
return h[i].score > h[j].score
}
func (h jumpHeap) Swap(i, j int) {
h[i], h[j] = h[j], h[i]
}
func (h *jumpHeap) Push(x any) {
*h = append(*h, x.(jumpEntry))
}
func (h *jumpHeap) Pop() any {
a := *h
x := a[len(a)-1]
*h = a[:len(a)-1]
return x
}
func maxJumpScore(nums []int) int64 {
if len(nums) == 0 {
return -1
}
h := &jumpHeap{
jumpEntry{
int64(nums[0]),
nums[0],
},
}
score := int64(nums[0])
for i := 1; i < len(nums); i++ {
for h.Len() > 0 && (*h)[0].end < i {
heap.Pop(h)
}
if h.Len() == 0 {
return -1
}
score = (*h)[0].score + int64(nums[i])
heap.Push(h, jumpEntry{score, i + nums[i]})
}
return score
}
复杂度分析
- 时间复杂度：$O(n \log n)$。
- 空间复杂度：额外空间 $O(n)$。
关键点总结
[!green]
堆按收益选最优，右界决定候选是否有效；收益较小的过期元素可以等到成为堆顶时再删除。
易错点总结
[!yellow]
先剔除过期候选；不能只选最远跳点；中途得到的高分若不能到终点不算答案。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 239. 滑动窗口最大值 | 困难 | 都维护未过期候选的最大值，但本题每个前驱的有效右界不同，不能直接套固定宽度出队规则。 |
| 656. 成本最小路径 | 困难 | 都在只能向右跳的有向无环结构上按可达前驱或后继做最优值 DP；该题最小化路径成本且跳长上限固定，本题最大化积分且每个位置的可达范围不同。 |