【每日一题Day355】LC1402 做菜顺序

顺序"/>

【每日一题Day355】LC1402 做菜顺序

做菜顺序【LC1402】

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

一道菜的 「 like-time 系数 」定义为烹饪这道菜结束的时间（包含之前每道菜所花费的时间）乘以这道菜的满意程度，也就是 time[i]*satisfaction[i] 。

返回厨师在准备了一定数量的菜肴后可以获得的最大 like-time 系数 总和。

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

• 思路

  • 贪心：
    • 为了获得最大的 like-time 系数 总和，应按照满意度升序做菜；
    • 满意度大的最后再做；
    • 满意度为负数的菜，可以选择做或者不做。
  • 排序后倒序遍历，增加一道菜like-time系数变化量为：satisfaction[i] +…+ satisfaction[n-1]，如果大于0，那么可以使 like-time 系数 总和增加，那么选择做这道菜

• 实现

  class Solution {public int maxSatisfaction(int[] satisfaction) {// 贪心：为了获得最大的 like-time 系数 总和，应按照满意度升序做菜；满意度大的最后再做；满意度为负数的菜，可以选择做或者不做// 大于等于0的菜必做，然后选择负数的菜作为第一道菜，看其能否使like-time系数// 排序后倒序遍历：每增加一道菜like-time系数变化量为：satisfaction[i] +....+ satisfaction[n-1]Arrays.sort(satisfaction);int n = satisfaction.length;if (satisfaction[n - 1] <= 0) return 0;int sum = 0, res = 0;for (int i = n - 1; i >= 0; i--){sum += satisfaction[i];if (sum > 0){res += sum;}else{break;}}return res;}
  }
  

  • 复杂度
    • 时间复杂度： O ( n log ⁡ n ) O(n \log n) O(nlogn)
    • 空间复杂度： O ( log ⁡ n ) O(\log n) O(logn)