Medium

题目描述

你被未来体育科学家给出了两个长度相同的整数数组 energyDrinkA 和 energyDrinkB，长度为 n。这些数组分别表示两种不同能量饮品 A 和 B 每小时提供的能量提升。

你想通过每小时喝一种能量饮品来最大化总能量提升。但是，如果你想从喝一种能量饮品切换到另一种，你需要等待一小时来清洁你的系统（意味着在那一小时你不会获得任何能量提升）。

返回在接下来 n 小时内你能获得的最大总能量提升。

注意你可以开始喝两种能量饮品中的任何一种。

示例 1：

输入：energyDrinkA = [1,3,1], energyDrinkB = [3,1,1]
输出：5
解释：
要获得 5 的能量提升，只喝能量饮品 A（或只喝 B）。

示例 2：

输入：energyDrinkA = [4,1,1], energyDrinkB = [1,1,3]
输出：7
解释：
要获得 7 的能量提升：
- 第一小时喝能量饮品 A。
- 切换到能量饮品 B，我们失去第二小时的能量提升。
- 第三小时获得饮品 B 的能量提升。

约束条件：

  • n == energyDrinkA.length == energyDrinkB.length
  • 3 <= n <= 10^5
  • 1 <= energyDrinkA[i], energyDrinkB[i] <= 10^5

解题思路

这是一个经典的动态规划问题。我们需要考虑在每个时刻选择喝哪种饮品能获得最大收益。

核心思路： 定义状态：

  • dpA[i] 表示前 i+1 小时内，第 i 小时喝饮品 A 时能获得的最大能量
  • dpB[i] 表示前 i+1 小时内，第 i 小时喝饮品 B 时能获得的最大能量

状态转移：

  • 如果第 i 小时喝 A，有两种选择：
    1. 前一小时也喝 A：dpA[i-1] + energyDrinkA[i]
    2. 前一小时喝 B，需要跳过第 i-1 小时：dpB[i-2] + energyDrinkA[i]
  • 同理，如果第 i 小时喝 B：
    1. 前一小时也喝 B：dpB[i-1] + energyDrinkB[i]
    2. 前一小时喝 A，需要跳过第 i-1 小时：dpA[i-2] + energyDrinkB[i]

边界条件：

  • 第 0 小时只能选择其中一种饮品
  • 第 1 小时可以继续喝第 0 小时的饮品，或者切换（但不能获得第 1 小时的收益）

最终答案是 max(dpA[n-1], dpB[n-1])。

这种方法的优点是思路清晰，状态转移明确，时间复杂度为 O(n)，空间复杂度也可以优化到 O(1)。

代码实现

class Solution {
public:
    long long maxEnergyBoost(vector<int>& energyDrinkA, vector<int>& energyDrinkB) {
        int n = energyDrinkA.size();
        
        // dpA[i]: 第i小时喝A时的最大能量
        // dpB[i]: 第i小时喝B时的最大能量
        vector<long long> dpA(n), dpB(n);
        
        // 初始状态
        dpA[0] = energyDrinkA[0];
        dpB[0] = energyDrinkB[0];
        
        if (n > 1) {
            dpA[1] = dpA[0] + energyDrinkA[1];
            dpB[1] = dpB[0] + energyDrinkB[1];
        }
        
        // 状态转移
        for (int i = 2; i < n; i++) {
            dpA[i] = max(dpA[i-1], dpB[i-2]) + energyDrinkA[i];
            dpB[i] = max(dpB[i-1], dpA[i-2]) + energyDrinkB[i];
        }
        
        return max(dpA[n-1], dpB[n-1]);
    }
};

class Solution:
    def maxEnergyBoost(self, energyDrinkA: List[int], energyDrinkB: List[int]) -> int:
        n = len(energyDrinkA)
        
        # dpA[i]: 第i小时喝A时的最大能量
        # dpB[i]: 第i小时喝B时的最大能量
        dpA = [0] * n
        dpB = [0] * n
        
        # 初始状态
        dpA[0] = energyDrinkA[0]
        dpB[0] = energyDrinkB[0]
        
        if n > 1:
            dpA[1] = dpA[0] + energyDrinkA[1]
            dpB[1] = dpB[0] + energyDrinkB[1]
        
        # 状态转移
        for i in range(2, n):
            dpA[i] = max(dpA[i-1], dpB[i-2]) + energyDrinkA[i]
            dpB[i] = max(dpB[i-1], dpA[i-2]) + energyDrinkB[i]
        
        return max(dpA[n-1], dpB[n-1])

public class Solution {
    public long MaxEnergyBoost(int[] energyDrinkA, int[] energyDrinkB) {
        int n = energyDrinkA.Length;
        
        // dpA[i]: 第i小时喝A时的最大能量
        // dpB[i]: 第i小时喝B时的最大能量
        long[] dpA = new long[n];
        long[] dpB = new long[n];
        
        // 初始状态
        dpA[0] = energyDrinkA[0];
        dpB[0] = energyDrinkB[0];
        
        if (n > 1) {
            dpA[1] = dpA[0] + energyDrinkA[1];
            dpB[1] = dpB[0] + energyDrinkB[1];
        }
        
        // 状态转移
        for (int i = 2; i < n; i++) {
            dpA[i] = Math.Max(dpA[i-1], dpB[i-2]) + energyDrinkA[i];
            dpB[i] = Math.Max(dpB[i-1], dpA[i-2]) + energyDrinkB[i];
        }
        
        return Math.Max(dpA[n-1], dpB[n-1]);
    }
}

var maxEnergyBoost = function(energyDrinkA, energyDrinkB) {
    const n = energyDrinkA.length;
    
    // dpA[i]: 第i小时喝A时的最大能量
    // dpB[i]: 第i小时喝B时的最大能量
    const dpA = new Array(n);
    const dpB = new Array(n);
    
    // 初始状态
    dpA[0] = energyDrinkA[0];
    dpB[0] = energyDrinkB[0];
    
    if (n > 1) {
        dpA[1] = dpA[0] + energyDrinkA[1];
        dpB[1] = dpB[0] + energyDrinkB[1];
    }
    
    // 状态转移
    for (let i = 2; i < n; i++) {
        dpA[i] = Math.max(dpA[i-1], dpB[i-2]) + energyDrinkA[i];
        dpB[i] = Math.max(dpB[i-1], dpA[i-2]) + energyDrinkB[i];
    }
    
    return Math.max(dpA[n-1], dpB[n-1]);
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度
时间复杂度O(n)
空间复杂度O(n)

说明：

  • 时间复杂度：需要遍历数组一次，每个位置的状态转移是 O(1) 操作
  • 空间复杂度：使用了两个长度为 n 的数组存储 dp 状态，可以进一步优化为 O(1)（只保存前两个状态）