Medium

题目描述

给你两个整数数组 skill 和 mana，长度分别为 n 和 m。

在实验室中，n 个巫师必须按顺序冲泡 m 个魔法药剂。每个魔法药剂都有一个法力容量 mana[j]，必须依次通过所有巫师才能正确冲泡。第 i 个巫师在第 j 个魔法药剂上花费的时间是 time[i][j] = skill[i] * mana[j]。

由于冲泡过程很精细，魔法药剂必须在当前巫师完成工作后立即传递给下一个巫师。这意味着时间必须同步，以便每个巫师在魔法药剂到达时立即开始工作。

返回正确冲泡魔法药剂所需的最小时间。

示例 1：

输入：skill = [1,5,2,4], mana = [5,1,4,2]
输出：110

示例 2：

输入：skill = [1,1,1], mana = [1,1,1]
输出：5

示例 3：

输入：skill = [1,2,3,4], mana = [1,2]
输出：21

约束条件：

  • n == skill.length
  • m == mana.length
  • 1 <= n, m <= 5000
  • 1 <= mana[i], skill[i] <= 5000

解题思路

这是一个模拟问题，核心在于理解魔法药剂的流水线处理过程。

问题分析：

  • 每个魔法药剂必须按顺序经过所有巫师
  • 魔法药剂必须在前一个巫师完成后立即传递给下一个巫师
  • 需要维护每个巫师的空闲时间，确保时间同步

解题思路：

  1. 维护一个数组 f[i] 表示第 i 个巫师完成当前魔法药剂的最早时间
  2. 对于每个新的魔法药剂，从第一个巫师开始：
    • 第一个巫师的开始时间是当前空闲时间 f[0]
    • 后续巫师的开始时间是 max(前一个巫师完成时间, 自己的空闲时间)
  3. 更新所有巫师的空闲时间：
    • 最后一个巫师的完成时间就是这个魔法药剂的总完成时间
    • 从后往前推算每个巫师的完成时间

关键点：

  • 使用贪心策略，每个魔法药剂尽早开始
  • 正确维护时间同步约束
  • 从后往前更新空闲时间，确保时间一致性

代码实现

class Solution {
public:
    long long minTime(vector<int>& skill, vector<int>& mana) {
        int n = skill.size();
        vector<long long> f(n, 0); // f[i] 表示第i个巫师的空闲时间
        
        for (int x : mana) {
            long long now = f[0]; // 从第一个巫师的空闲时间开始
            
            // 计算这个魔法药剂通过所有巫师的时间
            for (int i = 1; i < n; i++) {
                now = max(now + (long long)skill[i-1] * x, f[i]);
            }
            
            // 最后一个巫师完成时间
            f[n-1] = now + (long long)skill[n-1] * x;
            
            // 从后往前更新每个巫师的空闲时间
            for (int i = n-2; i >= 0; i--) {
                f[i] = f[i+1] - (long long)skill[i+1] * x;
            }
        }
        
        return f[n-1];
    }
};

class Solution:
    def minTime(self, skill: List[int], mana: List[int]) -> int:
        n = len(skill)
        f = [0] * n  # f[i] 表示第i个巫师的空闲时间
        
        for x in mana:
            now = f[0]  # 从第一个巫师的空闲时间开始
            
            # 计算这个魔法药剂通过所有巫师的时间
            for i in range(1, n):
                now = max(now + skill[i-1] * x, f[i])
            
            # 最后一个巫师完成时间
            f[n-1] = now + skill[n-1] * x
            
            # 从后往前更新每个巫师的空闲时间
            for i in range(n-2, -1, -1):
                f[i] = f[i+1] - skill[i+1] * x
        
        return f[n-1]

public class Solution {
    public long MinTime(int[] skill, int[] mana) {
        int n = skill.Length;
        long[] f = new long[n]; // f[i] 表示第i个巫师的空闲时间
        
        foreach (int x in mana) {
            long now = f[0]; // 从第一个巫师的空闲时间开始
            
            // 计算这个魔法药剂通过所有巫师的时间
            for (int i = 1; i < n; i++) {
                now = Math.Max(now + (long)skill[i-1] * x, f[i]);
            }
            
            // 最后一个巫师完成时间
            f[n-1] = now + (long)skill[n-1] * x;
            
            // 从后往前更新每个巫师的空闲时间
            for (int i = n-2; i >= 0; i--) {
                f[i] = f[i+1] - (long)skill[i+1] * x;
            }
        }
        
        return f[n-1];
    }
}

var minTime = function(skill, mana) {
    const n = skill.length;
    const f = new Array(n).fill(0); // f[i] 表示第i个巫师的空闲时间
    
    for (const x of mana) {
        let now = f[0]; // 从第一个巫师的空闲时间开始
        
        // 计算这个魔法药剂通过所有巫师的时间
        for (let i = 1; i < n; i++) {
            now = Math.max(now + skill[i-1] * x, f[i]);
        }
        
        // 最后一个巫师完成时间
        f[n-1] = now + skill[n-1] * x;
        
        // 从后往前更新每个巫师的空闲时间
        for (let i = n-2; i >= 0; i--) {
            f[i] = f[i+1] - skill[i+1] * x;
        }
    }
    
    return f[n-1];
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值
时间复杂度O(m × n)，其中 m 是魔法药剂数量，n 是巫师数量
空间复杂度O(n)，用于存储每个巫师的空闲时间