千问 LeetCode 1402做菜顺序 public int maxSatisfaction(int[] satisfaction)

张开发
• 2026/4/20 0:36:29 • 15 分钟阅读

最新文章

推荐文章

相关文章

分享文章

千问 LeetCode 1402做菜顺序 public int maxSatisfaction(int[] satisfaction)
这道题其实是一个经典的“排序 + 贪心”问题。它的核心直觉是：为了获得最大的总分，我们应该把“满意度”最高的菜放在最后做（系数最大），把满意度低的菜放在前面做。💡 核心思路：贪心算法为什么需要排序？假设我们选了两道菜，满意度分别是 A 和 B，且 A A，所以 B - A 0。这意味着把满意度高的菜往后放（系数大），得分总是更高。因此，第一步必须是对 satisfaction 数组进行从小到大排序。如何决定做哪些菜？排序后，问题变成了：从排序后的数组末尾开始，向前选取多少道菜？我们可以从后往前遍历（从满意度最高的菜开始选），并维护一个后缀和。- 每当我们决定把一道新菜（满意度为 s）加入到烹饪计划的最前面时，这道菜的系数是 1，而原本计划中所有菜的系数都会加 1。- 所以，总得分的增加量 = s + (text{当前已选菜的总满意度})。- 只要这个增加量是正数，我们就应该把这道菜加进来；如果增加量变成了负数或 0，说明再加更差的菜只会拖累总分，应该停止。🧮 算法步骤1. 排序：将 satisfaction 数组从小到大排序。2. 倒序遍历：从数组最后一个元素开始向前遍历。3. 累加判断： - 维护一个变量 suffixSum（当前已选菜的满意度之和）。 - 维护一个变量 totalScore（当前的总得分）。 - 对于当前遍历到的菜 s，如果 suffixSum + s 0，说明把这道菜加在最前面能让总分变大。 - 更新 suffixSum += s。 - 更新 totalScore += suffixSum（注意：这里利用了一个数学技巧，新总分 = 旧总分 + 新的后缀和）。4. 返回结果。💻 代码实现import java.util.Arrays;class Solution { public int maxSatisfaction(int[] satisfaction) { // 1. 排序：从小到大 Arrays.sort(satisfaction); int totalScore = 0; // 总得分 int suffixSum = 0; // 当前已选菜的满意度之和（后缀和） // 2. 从后往前遍历（贪心策略：先选满意度最高的） for (int i = satisfaction.length - 1; i = 0; i--) { int currentSatisfaction = satisfaction[i]; // 3. 判断是否要加入这道菜 // 如果加入这道菜后，后缀和（即总得分的增量）大于0，则加入 if (suffixSum + currentSatisfaction 0) {

更多文章