LeetCode 题解工作台
销售价值减少的颜色球
你有一些球的库存 inventory ，里面包含着不同颜色的球。一个顾客想要 任意颜色 总数为 orders 的球。 这位顾客有一种特殊的方式衡量球的价值：每个球的价值是目前剩下的 同色球 的数目。比方说还剩下 6 个黄球，那么顾客买第一个黄球的时候该黄球的价值为 6 。这笔交易以后，只剩下 5 个…
6
题型
4
代码语言
3
相关题
当前训练重点
中等 · 二分·搜索·答案·空间
答案摘要
要使得总价值最大，我们可以贪心地每次卖出数量最多的一种颜色的球。由于 `orders` 值域较大，如果直接简单地模拟，会超时。因此，我们需要优化模拟的过程。 实际上，我们不需要一次次进行模拟，我们可以跟踪数量最多的同色球的种类数 `cnt`，每一次可以卖出一批球，从而达到加速模拟的目的。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 二分·搜索·答案·空间 题型思路
题目描述
你有一些球的库存 inventory ，里面包含着不同颜色的球。一个顾客想要 任意颜色 总数为 orders 的球。
这位顾客有一种特殊的方式衡量球的价值：每个球的价值是目前剩下的 同色球 的数目。比方说还剩下 6 个黄球，那么顾客买第一个黄球的时候该黄球的价值为 6 。这笔交易以后，只剩下 5 个黄球了，所以下一个黄球的价值为 5 （也就是球的价值随着顾客购买同色球是递减的）
给你整数数组 inventory ，其中 inventory[i] 表示第 i 种颜色球一开始的数目。同时给你整数 orders ，表示顾客总共想买的球数目。你可以按照 任意顺序 卖球。
请你返回卖了 orders 个球以后 最大 总价值之和。由于答案可能会很大，请你返回答案对 109 + 7 取余数 的结果。
示例 1：
输入：inventory = [2,5], orders = 4 输出：14 解释：卖 1 个第一种颜色的球（价值为 2 )，卖 3 个第二种颜色的球（价值为 5 + 4 + 3）。 最大总和为 2 + 5 + 4 + 3 = 14 。
示例 2：
输入：inventory = [3,5], orders = 6 输出：19 解释：卖 2 个第一种颜色的球（价值为 3 + 2），卖 4 个第二种颜色的球（价值为 5 + 4 + 3 + 2）。 最大总和为 3 + 2 + 5 + 4 + 3 + 2 = 19 。
示例 3：
输入：inventory = [2,8,4,10,6], orders = 20 输出：110
示例 4：
输入：inventory = [1000000000], orders = 1000000000 输出：21 解释：卖 1000000000 次第一种颜色的球，总价值为 500000000500000000 。 500000000500000000 对 109 + 7 取余为 21 。
提示：
1 <= inventory.length <= 1051 <= inventory[i] <= 1091 <= orders <= min(sum(inventory[i]), 109)
解题思路
方法一：贪心 + 优化模拟
要使得总价值最大，我们可以贪心地每次卖出数量最多的一种颜色的球。由于 orders 值域较大，如果直接简单地模拟，会超时。因此，我们需要优化模拟的过程。
实际上，我们不需要一次次进行模拟，我们可以跟踪数量最多的同色球的种类数 cnt，每一次可以卖出一批球，从而达到加速模拟的目的。
时间复杂度 ，空间复杂度 。其中 为数组 inventory 的长度。
class Solution:
def maxProfit(self, inventory: List[int], orders: int) -> int:
inventory.sort(reverse=True)
mod = 10**9 + 7
ans = i = 0
n = len(inventory)
while orders > 0:
while i < n and inventory[i] >= inventory[0]:
i += 1
nxt = 0
if i < n:
nxt = inventory[i]
cnt = i
x = inventory[0] - nxt
tot = cnt * x
if tot > orders:
decr = orders // cnt
a1, an = inventory[0] - decr + 1, inventory[0]
ans += (a1 + an) * decr // 2 * cnt
ans += (inventory[0] - decr) * (orders % cnt)
else:
a1, an = nxt + 1, inventory[0]
ans += (a1 + an) * x // 2 * cnt
inventory[0] = nxt
orders -= tot
ans %= mod
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Checks if the candidate uses binary search effectively over the range of possible values.
- question_mark
Evaluates the candidate's ability to implement a greedy strategy for maximizing value.
- question_mark
Looks for the candidate’s ability to optimize space and time complexity for large inputs.
常见陷阱
外企场景- error
Failing to properly handle the diminishing value of balls as they are sold, which leads to incorrect total value calculations.
- error
Not using binary search effectively over the answer space, leading to suboptimal performance.
- error
Improperly calculating the total value from each color, potentially overestimating how many balls can be sold.
进阶变体
外企场景- arrow_right_alt
What if the number of balls in inventory is fixed, but the number of orders varies?
- arrow_right_alt
What if the customer orders a very small number of balls compared to the inventory?
- arrow_right_alt
What if the inventory contains very large numbers of balls, requiring careful handling of big integer arithmetic?