LeetCode 题解工作台
购买两块巧克力
给你一个整数数组 prices ，它表示一个商店里若干巧克力的价格。同时给你一个整数 money ，表示你一开始拥有的钱数。 你必须购买 恰好 两块巧克力，而且剩余的钱数必须是 非负数 。同时你想最小化购买两块巧克力的总花费。 请你返回在购买两块巧克力后，最多能剩下多少钱。如果购买任意两块巧克力都超…
3
题型
6
代码语言
3
相关题
当前训练重点
简单 · 贪心·invariant
答案摘要
我们可以将巧克力的价格从小到大排序，然后取前两个价格相加，就是我们购买两块巧克力的最小花费 。如果这个花费大于我们拥有的钱数，那么我们就返回 `money`，否则返回 `money - cost`。 时间复杂度 $O(n \times \log n)$，空间复杂度 $O(\log n)$。其中 是数组 `prices` 的长度。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 贪心·invariant 题型思路
题目描述
给你一个整数数组 prices ，它表示一个商店里若干巧克力的价格。同时给你一个整数 money ，表示你一开始拥有的钱数。
你必须购买 恰好 两块巧克力，而且剩余的钱数必须是 非负数 。同时你想最小化购买两块巧克力的总花费。
请你返回在购买两块巧克力后，最多能剩下多少钱。如果购买任意两块巧克力都超过了你拥有的钱，请你返回 money 。注意剩余钱数必须是非负数。
示例 1：
输入：prices = [1,2,2], money = 3 输出：0 解释：分别购买价格为 1 和 2 的巧克力。你剩下 3 - 3 = 0 块钱。所以我们返回 0 。
示例 2：
输入：prices = [3,2,3], money = 3 输出：3 解释：购买任意 2 块巧克力都会超过你拥有的钱数，所以我们返回 3 。
提示：
2 <= prices.length <= 501 <= prices[i] <= 1001 <= money <= 100
解题思路
方法一：排序
我们可以将巧克力的价格从小到大排序，然后取前两个价格相加，就是我们购买两块巧克力的最小花费 。如果这个花费大于我们拥有的钱数，那么我们就返回 money，否则返回 money - cost。
时间复杂度 ，空间复杂度 。其中 是数组 prices 的长度。
class Solution:
def buyChoco(self, prices: List[int], money: int) -> int:
prices.sort()
cost = prices[0] + prices[1]
return money if money < cost else money - cost
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | O(n) |
| 空间 | O(1) |
面试官常问的追问
外企场景- question_mark
Are you using the two cheapest chocolates to minimize cost?
- question_mark
Did you consider what happens if money is insufficient for any two chocolates?
- question_mark
Can you solve this without sorting the entire array?
常见陷阱
外企场景- error
Failing to check if money is enough before subtracting prices.
- error
Choosing any two chocolates without ensuring the sum is minimal.
- error
Assuming leftover can be negative, violating the non-negative requirement.
进阶变体
外企场景- arrow_right_alt
Buy three chocolates instead of two, still minimizing total cost.
- arrow_right_alt
Maximize leftover money rather than minimizing chocolate cost.
- arrow_right_alt
Allow repeated purchase of the same chocolate if prices permit.