LEETCODE 1402. Reducing Dishes 解题思路分析

题目大意：

做菜顺序

一个厨师收集了他 n 道菜的满意程度 satisfaction ，这个厨师做出每道菜的时间都是 1 单位时间。

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

请你返回做完所有菜 「喜爱时间」总和的最大值为多少。

你可以按 任意 顺序安排做菜的顺序，你也可以选择放弃做某些菜来获得更大的总和。

示例 1：

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

示例 2：

输入：satisfaction = [4,3,2]
输出：20
解释：按照原来顺序相反的时间做菜 (2*1 + 3*2 + 4*3 = 20)

示例 3：

输入：satisfaction = [-1,-4,-5]
输出：0
解释：大家都不喜欢这些菜，所以不做任何菜可以获得最大的喜爱时间系数。

示例 4：

输入：satisfaction = [-2,5,-1,0,3,-3]
输出：35

---

提示：

• n == satisfaction.length
• 1 <= n <= 500
• -10^3 <= satisfaction[i] <= 10^3

---

如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=1402

解题思路分析：

解法一：

本题总得分的计算公式为：

sum=1*satisfaction[0] + 2*satisfaction[1] + 3*satisfaction[2]+...
    n*satisfaction[n-1];

由于较大数乘以较大数的乘积会更大，并且1到n是递增排列，因此，satisfaction数组中的数值也是递增排列的话，那么最终的计算结果一定是最大的。不过题目中说我们可以放弃掉一些菜以便获得更大积分，放弃哪些菜可以使得积分变大我们很难一眼看出，不过本题的数据规模并不大，因此我们完全可以采用n平方的时间复杂度去逐个尝试。

解题步骤：

1. 先将 satisfaction 数组升序排序。
2. 用数组中每一个数字乘以相应下标（下标从1开始），并累加所有乘积的和，得到一个结果sum。
3. 删除数组中最小的元素（首元素），再按照第2条的逻辑计算出一个结果sum，并比较上个sum，得出全局最大值
4. 重复步骤3，直到数组中没有元素，全局最大值即是返回结果。

实现代码：

public int maxSatisfaction(int[] satisfaction) {
    Arrays.sort(satisfaction); // 排序数组
    int max=0; // 全局最大值
    // 数组起始位置
    for(int i=0;i<satisfaction.length;i++){
        int sum=0; // 计算总和
        int time=1; // 下标（从1开始）
        // 从起始位置循环至数组末尾，计算总和
        for(int j=i;j<satisfaction.length;j++,time++){
            sum+=(time*satisfaction[j]);
        }
        // 更新全局最大值
        max=Math.max(max,sum);
    }
    return max;
}

本题解法执行时间为2ms。

Runtime: 2 ms, faster than 53.40% of Java online submissions for Reducing Dishes.

Memory Usage: 37.8 MB, less than 100.00% of Java online submissions for Reducing Dishes.

---

解法二：

其实本题可以将时间复杂度降为n。核心思想还是解法一中的算法，较大数乘以较大数的乘积会更大，因此，我们可以从满意度最高的菜开始着手。举例来说明，比如我们有5道菜，满意度分别是(已排序): [-20, -3, 1, 2, 9]，明显9是最大值，我们先做满意度为9的那一道菜，即：

sum = 9 * 1 = 9;

接下来是关键，我们尝试在做9之前先做2，那么sum会变为：

sum = 2 * 1 + 9 * 2 = 20;
// 也可以表示为：
sum =         9 * 1
    + 2 * 1 + 9 * 1;

也许你还没看出什么门道，我们继续尝试在做2之前先做1：

sum = 1 * 1 + 2 * 2 + 9 * 3 = 32;
// 也可以表示为：
sum =                 9 * 1
    +         2 * 1 + 9 * 1
    + 1 * 1 + 2 * 1 + 9 * 1;

我们发现，每在前面插入一道菜，sum会变为：原sum再加上当前所有已选择菜的满意度之和。我们不妨再继续尝试在做1之前先做-3：

sum = -3 * 1 + 1 * 2 + 2 * 3 + 9 * 4 = 41;
// 也可以表示为：
sum =                          9 * 1
    +                  2 * 1 + 9 * 1
    +          1 * 1 + 2 * 1 + 9 * 1
    + -3 * 1 + 1 * 1 + 2 * 1 + 9 * 1;

虽然我们加入了一个满意度为负数-3的菜，但sum还是在增加，我们继续尝试在做-3之前先做-20：

sum = -3 * 1 + 1 * 2 + 2 * 3 + 9 * 4 = 30;
// 也可以表示为：
sum =                                    9 * 1
    +                            2 * 1 + 9 * 1
    +                    1 * 1 + 2 * 1 + 9 * 1
    +           -3 * 1 + 1 * 1 + 2 * 1 + 9 * 1
    + -20 * 1 + -3 * 1 + 1 * 1 + 2 * 1 + 9 * 1;

我们发现sum值较前一次变小了。原因在于，相对于前一次的sum，这一次加入到sum的数值为上述代码的最后一行：

-20 * 1 + -3 * 1 + 1 * 1 + 2 * 1 + 9 * 1 = -11;

这最后一行其实也就是当前所有已选菜的满意度之和，这个和如果是负数，那么加入到总的sum一定会使其变小，因此，到此为止，我们的思路就变得清晰起来，我们总结一下解题步骤：

1. 建立一个变量s代表所有已选菜的满意度和，初始为0。另外建立一个变量sum代表所有菜的[喜爱时间]和，初始值也为0。
2. 将数组按照升序排序。
3. 从数组最后一位开始向前循环，取出当前数字，累加至s。如果s大于0，将s累加至sum。如果s小于0，退出循环，返回sum。

实现代码：

public int maxSatisfaction(int[] satisfaction) {
    Arrays.sort(satisfaction);
    int s=0;
    int sum=0;
    for(int i=satisfaction.length-1;i>=0;i--){
        s+=satisfaction[i];
        if(s>0) sum+=s;
        else break;
    }
    return sum;
}

本题解法执行时间为1ms。

Runtime: 1 ms, faster than 100.00% of Java online submissions for Reducing Dishes.

Memory Usage: 37.5 MB, less than 100.00% of Java online submissions for Reducing Dishes.

本网站文章均为原创内容，并可随意转载，但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: https://leetcode.jp/leetcode-1402-reducing-dishes-解题思路分析/