LeetCode 题解工作台
打折购买糖果的最小开销
一家商店正在打折销售糖果。每购买 两个 糖果，商店会 免费 送一个糖果。 免费送的糖果唯一的限制是：它的价格需要小于等于购买的两个糖果价格的 较小值 。 比方说，总共有 4 个糖果，价格分别为 1 ， 2 ， 3 和 4 ，一位顾客买了价格为 2 和 3 的糖果，那么他可以免费获得价格为 1 的糖果…
3
题型
5
代码语言
3
相关题
当前训练重点
简单 · 贪心·invariant
答案摘要
我们可以先将糖果按照价格从高到低排序，然后每三个糖果中取两个糖果，这样可以保证免费获得的糖果价格最高，从而使得总开销最小。 时间复杂度 $O(n \times \log n)$，空间复杂度 $O(\log n)$。其中 是糖果数。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 贪心·invariant 题型思路
题目描述
一家商店正在打折销售糖果。每购买 两个 糖果，商店会 免费 送一个糖果。
免费送的糖果唯一的限制是：它的价格需要小于等于购买的两个糖果价格的 较小值 。
- 比方说，总共有
4个糖果，价格分别为1，2，3和4，一位顾客买了价格为2和3的糖果，那么他可以免费获得价格为1的糖果，但不能获得价格为4的糖果。
给你一个下标从 0 开始的整数数组 cost ，其中 cost[i] 表示第 i 个糖果的价格，请你返回获得 所有 糖果的 最小 总开销。
示例 1：
输入：cost = [1,2,3] 输出：5 解释：我们购买价格为 2 和 3 的糖果，然后免费获得价格为 1 的糖果。 总开销为 2 + 3 = 5 。这是开销最小的 唯一 方案。 注意，我们不能购买价格为 1 和 3 的糖果，并免费获得价格为 2 的糖果。 这是因为免费糖果的价格必须小于等于购买的 2 个糖果价格的较小值。
示例 2：
输入：cost = [6,5,7,9,2,2] 输出：23 解释：最小总开销购买糖果方案为： - 购买价格为 9 和 7 的糖果 - 免费获得价格为 6 的糖果 - 购买价格为 5 和 2 的糖果 - 免费获得价格为 2 的最后一个糖果 因此，最小总开销为 9 + 7 + 5 + 2 = 23 。
示例 3：
输入：cost = [5,5] 输出：10 解释：由于只有 2 个糖果，我们需要将它们都购买，而且没有免费糖果。 所以总最小开销为 5 + 5 = 10 。
提示：
1 <= cost.length <= 1001 <= cost[i] <= 100
解题思路
方法一：贪心
我们可以先将糖果按照价格从高到低排序，然后每三个糖果中取两个糖果，这样可以保证免费获得的糖果价格最高，从而使得总开销最小。
时间复杂度 ，空间复杂度 。其中 是糖果数。
class Solution:
def minimumCost(self, cost: List[int]) -> int:
cost.sort(reverse=True)
return sum(cost) - sum(cost[2::3])
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
The candidate should recognize the greedy approach to minimize the total cost by selecting the least expensive candy for free.
- question_mark
The candidate should explain how sorting the array affects the strategy and ensures the discount maximizes the total savings.
- question_mark
The candidate should be aware of edge cases like fewer than three candies and explain how the solution handles them.
常见陷阱
外企场景- error
Not sorting the array before processing candies will lead to incorrect results, as the cheapest candy may not be the one chosen for the discount.
- error
Failing to handle edge cases, such as when there are fewer than three candies, can cause errors in the solution.
- error
Overcomplicating the solution by trying to find the best combination of candies without using a greedy approach.
进阶变体
外企场景- arrow_right_alt
Change the candy count or price range to see how the approach scales with different inputs.
- arrow_right_alt
Introduce multiple discount strategies, such as giving a discount after every 4th candy or offering a fixed discount on each candy.
- arrow_right_alt
Allow the customer to choose any candy for free, not necessarily the least expensive, to create a new variant of the problem.