Hard

题目描述

一位厨师收集了他 n 道菜的满意程度数据。厨师可以在 1 个单位时间内做好任何一道菜。

一道菜的 “喜爱时间” 系数定义为烹饪这道菜以及之前每道菜所花费的时间乘以这道菜的满意程度，即 time[i] * satisfaction[i]。

返回厨师在制作若干道菜后可以获得的最大 “喜爱时间” 系数总和。

可以按任意顺序制作菜肴，厨师可以丢弃一些菜肴来获得这个最大值。

示例 1：

输入：satisfaction = [-1,-8,0,5,-9]
输出：14
解释：去掉第二道和最后一道菜，最大的 "喜爱时间" 系数和为 (-1*1 + 0*2 + 5*3 = 14)。
每道菜都需要一个单位时间来制作。

示例 2：

输入：satisfaction = [4,3,2]
输出：20
解释：可以按任意顺序制作菜肴，(2*1 + 3*2 + 4*3 = 20)

示例 3：

输入：satisfaction = [-1,-4,-5]
输出：0
解释：人们不喜欢这些菜。没有制作任何菜肴。

提示：

  • n == satisfaction.length
  • 1 <= n <= 500
  • -1000 <= satisfaction[i] <= 1000

解题思路

解题思路

这道题的关键在于理解如何安排菜肴的制作顺序以及选择哪些菜肴来制作。

核心观察：

  1. 为了使总的喜爱时间系数最大，满意度较高的菜应该安排在较后的时间制作（系数更大）
  2. 因此我们应该按满意度从小到大排序，然后考虑从后往前选择哪些菜肴

贪心策略：

  • 首先对数组按满意度升序排序
  • 从最高满意度开始，逐个考虑是否要包含当前菜肴
  • 关键insight：当我们在已选择的菜肴前面再加一道菜时，新加菜肴的系数是1，而之前所有菜肴的系数都增加1
  • 因此，新加一道菜带来的收益是：该菜的满意度 + 之前所有已选菜肴的满意度之和

算法步骤：

  1. 对满意度数组排序
  2. 从右向左遍历，维护当前已选菜肴的总满意度(sum)和总的喜爱时间系数(res)
  3. 对于每道新菜，如果 satisfaction[i] + sum > 0，则选择这道菜
  4. 更新sum和res

这个方法的正确性在于：如果加入当前菜肴后总收益为正，那么就应该加入；否则不加入。

代码实现

class Solution {
public:
    int maxSatisfaction(vector<int>& satisfaction) {
        sort(satisfaction.begin(), satisfaction.end());
        
        int res = 0, sum = 0;
        for (int i = satisfaction.size() - 1; i >= 0; i--) {
            sum += satisfaction[i];
            if (sum > 0) {
                res += sum;
            } else {
                break;
            }
        }
        
        return res;
    }
};

class Solution:
    def maxSatisfaction(self, satisfaction: List[int]) -> int:
        satisfaction.sort()
        
        res = sum_val = 0
        for i in range(len(satisfaction) - 1, -1, -1):
            sum_val += satisfaction[i]
            if sum_val > 0:
                res += sum_val
            else:
                break
        
        return res

public class Solution {
    public int MaxSatisfaction(int[] satisfaction) {
        Array.Sort(satisfaction);
        
        int res = 0, sum = 0;
        for (int i = satisfaction.Length - 1; i >= 0; i--) {
            sum += satisfaction[i];
            if (sum > 0) {
                res += sum;
            } else {
                break;
            }
        }
        
        return res;
    }
}

var maxSatisfaction = function(satisfaction) {
    satisfaction.sort((a, b) => a - b);
    
    let res = 0, sum = 0;
    for (let i = satisfaction.length - 1; i >= 0; i--) {
        sum += satisfaction[i];
        if (sum > 0) {
            res += sum;
        } else {
            break;
        }
    }
    
    return res;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(n log n)，主要是排序的时间复杂度
空间复杂度O(1)，只使用常数额外空间