Medium

题目描述

在一个神秘的地牢中，n 个魔法师站成一排。每个魔法师都有一个属性，可以给你能量。一些魔法师可能给你负能量，这意味着从你身上夺走能量。

你被诅咒了，在从魔法师 i 吸收能量后，你会立即被传送到魔法师 (i + k)。这个过程会重复，直到你到达 (i + k) 不存在的魔法师位置。

换句话说，你将选择一个起始点，然后以 k 步的跳跃进行传送，直到到达魔法师序列的末尾，在旅途中吸收所有能量。

给定一个数组 energy 和一个整数 k。返回你能获得的最大可能能量。

注意，当你到达一个魔法师时，你必须从他们那里获取能量，无论是负能量还是正能量。

示例 1：

输入：energy = [5,2,-10,-5,1], k = 3
输出：3
解释：我们可以从魔法师 1 开始获得总共 3 的能量，吸收 2 + 1 = 3。

示例 2：

输入：energy = [-2,-3,-1], k = 2
输出：-1
解释：我们可以从魔法师 2 开始获得总共 -1 的能量。

约束：

  • 1 <= energy.length <= 10^5
  • -1000 <= energy[i] <= 1000
  • 1 <= k <= energy.length - 1

提示：

  • 设 dp[i] 表示从索引 i 开始获得的能量。
  • 我们可以注意到，dp[i] = dp[i + k] + energy[i]。

解题思路

这是一道动态规划问题。关键观察是，从任意位置 i 开始，我们只能跳到位置 i+k, i+2k, i+3k… 直到超出数组边界。

解题思路：

  1. 核心状态转移方程：设 dp[i] 表示从位置 i 开始能获得的最大能量，则有 dp[i] = energy[i] + dp[i+k]（如果 i+k 在边界内）

  2. 边界条件：如果 i+k >= n，则 dp[i] = energy[i]（只能获得当前位置的能量）

  3. 遍历顺序：由于 dp[i] 依赖于 dp[i+k]，我们需要从后往前计算

  4. 优化思路：

    • 方法一：使用数组存储所有 dp 值
    • 方法二：由于每个位置只依赖于后面第 k 个位置，可以直接在原数组上修改，节省空间

  5. 答案计算：遍历所有可能的起始位置，返回最大的 dp 值

推荐使用方法二，时间复杂度 O(n)，空间复杂度 O(1)。

代码实现

class Solution {
public:
    int maximumEnergy(vector<int>& energy, int k) {
        int n = energy.size();
        
        // 从后往前计算，每个位置的最大能量
        for (int i = n - k - 1; i >= 0; i--) {
            energy[i] += energy[i + k];
        }
        
        // 找到所有可能起始位置的最大值
        int maxEnergy = INT_MIN;
        for (int i = 0; i < n; i++) {
            maxEnergy = max(maxEnergy, energy[i]);
        }
        
        return maxEnergy;
    }
};

class Solution:
    def maximumEnergy(self, energy: List[int], k: int) -> int:
        n = len(energy)
        
        # 从后往前计算，每个位置的最大能量
        for i in range(n - k - 1, -1, -1):
            energy[i] += energy[i + k]
        
        # 返回所有可能起始位置的最大值
        return max(energy)

public class Solution {
    public int MaximumEnergy(int[] energy, int k) {
        int n = energy.Length;
        
        // 从后往前计算，每个位置的最大能量
        for (int i = n - k - 1; i >= 0; i--) {
            energy[i] += energy[i + k];
        }
        
        // 找到所有可能起始位置的最大值
        int maxEnergy = int.MinValue;
        for (int i = 0; i < n; i++) {
            maxEnergy = Math.Max(maxEnergy, energy[i]);
        }
        
        return maxEnergy;
    }
}

/**
 * @param {number[]} energy
 * @param {number} k
 * @return {number}
 */
var maximumEnergy = function(energy, k) {
    const n = energy.length;
    
    // 从后往前计算，每个位置的最大能量
    for (let i = n - k - 1; i >= 0; i--) {
        energy[i] += energy[i + k];
    }
    
    // 返回所有可能起始位置的最大值
    return Math.max(...energy);
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值说明
时间复杂度O(n)需要遍历数组两次，一次计算dp值，一次找最大值
空间复杂度O(1)直接在原数组上修改，不需要额外空间