LeetCode 题解工作台
从魔法师身上吸取的最大能量
在神秘的地牢中， n 个魔法师站成一排。每个魔法师都拥有一个属性，这个属性可以给你提供能量。有些魔法师可能会给你负能量，即从你身上吸取能量。 你被施加了一种诅咒，当你从魔法师 i 处吸收能量后，你将被立即传送到魔法师 (i + k) 处。这一过程将重复进行，直到你到达一个不存在 (i + k) 的魔…
2
题型
6
代码语言
3
相关题
当前训练重点
中等 · 前缀和
答案摘要
我们可以在 $[n - k, n)$ 的范围内枚举终点，然后从终点开始向前遍历，每次累加间隔为 的魔法师的能量值，更新答案。 时间复杂度 ，其中 是数组 的长度。空间复杂度 。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 前缀和 题型思路
题目描述
在神秘的地牢中，n 个魔法师站成一排。每个魔法师都拥有一个属性，这个属性可以给你提供能量。有些魔法师可能会给你负能量，即从你身上吸取能量。
你被施加了一种诅咒，当你从魔法师 i 处吸收能量后，你将被立即传送到魔法师 (i + k) 处。这一过程将重复进行，直到你到达一个不存在 (i + k) 的魔法师为止。
换句话说，你将选择一个起点，然后以 k 为间隔跳跃，直到到达魔法师序列的末端，在过程中吸收所有的能量。
给定一个数组 energy 和一个整数k，返回你能获得的 最大 能量。
示例 1：
输入： energy = [5,2,-10,-5,1], k = 3
输出： 3
解释：可以从魔法师 1 开始，吸收能量 2 + 1 = 3。
示例 2：
输入： energy = [-2,-3,-1], k = 2
输出： -1
解释：可以从魔法师 2 开始，吸收能量 -1。
提示：
1 <= energy.length <= 105-1000 <= energy[i] <= 10001 <= k <= energy.length - 1
解题思路
方法一：枚举 + 逆序遍历
我们可以在 的范围内枚举终点，然后从终点开始向前遍历，每次累加间隔为 的魔法师的能量值，更新答案。
时间复杂度 ，其中 是数组 的长度。空间复杂度 。
class Solution:
def maximumEnergy(self, energy: List[int], k: int) -> int:
ans = -inf
n = len(energy)
for i in range(n - k, n):
j, s = i, 0
while j >= 0:
s += energy[j]
ans = max(ans, s)
j -= k
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(n) because each index is visited once in the backward dp computation, and space complexity is O(n) for storing the dp array. Prefix sums may reduce redundant sum calculations but do not increase asymptotic complexity. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Check if candidate identifies dp[i] as the energy from index i including jumps.
- question_mark
Look for recognition that negative energy can lower total if path choice is wrong.
- question_mark
Candidate should optimize using array plus prefix sum rather than brute-force simulation.
常见陷阱
外企场景- error
Failing to iterate from the end backward, causing dp values to be incorrect.
- error
Ignoring negative energy and assuming all jumps add energy.
- error
Recomputing sums for overlapping paths without using prefix sums.
进阶变体
外企场景- arrow_right_alt
Allowing variable jump sizes k[i] instead of a fixed k.
- arrow_right_alt
Modifying the dungeon so some magicians block teleportation to next jumps.
- arrow_right_alt
Changing the goal to minimize energy loss instead of maximizing gain.