【贪心+排序】【数组】【2023-10-22】
每一道菜都有一个满足程度(是一个整数),制作完成每道菜的时间为 1
,每一道的 [like-time系数] 定义为做菜的完成时间点乘以这道菜的满意度,求最大的 [like-time系数]。
我们把数组 satisfactions
记作 a
。
通过 示例1 我们可以判断出满意度越高的菜,我们越晚完成制作,于是需要给菜品满意度的数组排序,这里是降序排序,那么数组中的第一个元素就是满意度最高的菜品,那这个菜品什么时间点制作完成才会得到最大的 [like-time系数] 呢?
我们现在看一下制作 k
道菜,[like-time系数] f(k)
的值:
f ( k ) = k ⋅ a [ 0 ] + ( k − 1 ) ⋅ a [ 1 ] + . . . + 2 ⋅ a [ k − 1 ] + a [ k − 1 ] f(k) = k \cdot a[0] + (k-1) \cdot a[1] +...+ 2 \cdot a[k-1] + a[k-1] f(k)=k⋅a[0]+(k−1)⋅a[1]+...+2⋅a[k−1]+a[k−1]
f ( k ) = f ( k − 1 ) + ( a [ 0 ] + a [ 1 ] + . . . + a [ k − 2 ] ) f(k) = f(k-1) + (a[0] + a[1] + ... + a[k-2]) f(k)=f(k−1)+(a[0]+a[1]+...+a[k−2])
上式右侧是数组 a
的前缀和,我们可以一边遍历 a
,一边累加到前缀和变量 sum
中,于是可以快速通过 f(k-1)
计算出 f(k)
。
最终的答案就是 f(0), f(1), ..., f(n)
中的最大值。
值得关注的是,如果在某个时刻,前缀和 sum <= 0
,那么后面的 a[i]
必然都是负数,于是,我们在计算最大的 f(k)
时,只要计算遇到 sum <= 0
就退出for循环。其实for循环每循环一次计算得到的 f
就是对应的 f(k)
,一旦遇到 sum <= 0
就退出for循环,返回此时的 f
即可。
实现代码
class Solution {
public:
int maxSatisfaction(vector<int>& satisfaction) {
sort(satisfaction.rbegin(), satisfaction.rend());
int sum = 0;
int res = 0;
for (int satis : satisfaction) {
sum += satis;
if (sum < 0) break;
res += sum;
}
return res;
}
};
复杂度分析
时间复杂度: O ( n l o g n ) O(nlogn) O(nlogn), n n n 为数组的长度,该时间是排序的时间复杂度。
空间复杂度: O ( 1 ) O(1) O(1)。
如果文章内容有任何错误或者您对文章有任何疑问,欢迎私信博主或者在评论区指出 💬💬💬。
如果大家有更优的时间、空间复杂度方法,欢迎评论区交流。
最后,感谢您的阅读,如果感到有所收获的话可以给博主点一个 👍 哦。