LeetCode 题解工作台
购买物品的最大开销
给你一个下标从 0 开始大小为 m * n 的整数矩阵 values ，表示 m 个不同商店里 m * n 件不同的物品。每个商店有 n 件物品，第 i 个商店的第 j 件物品的价值为 values[i][j] 。除此以外，第 i 个商店的物品已经按照价值非递增排好序了，也就是说对于所有 0 都有 …
5
题型
5
代码语言
3
相关题
当前训练重点
困难 · 贪心·invariant
答案摘要
根据题目描述，我们应该优先选择价值越小的物品，把价值越大的物品留到后面购买，这样才能使得总开销最大。因此，我们使用优先队列（小根堆）存储每个商店中还未购买的最小价值的物品。初始时，我们将每个商店中最右边的物品加入优先队列。 在每一天，我们从优先队列中取出价值最小的物品，将其加入答案，并将该物品所在商店中的上一个物品加入优先队列。我们重复上述操作，直到优先队列为空。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 贪心·invariant 题型思路
题目描述
给你一个下标从 0 开始大小为 m * n 的整数矩阵 values ，表示 m 个不同商店里 m * n 件不同的物品。每个商店有 n 件物品，第 i 个商店的第 j 件物品的价值为 values[i][j] 。除此以外，第 i 个商店的物品已经按照价值非递增排好序了，也就是说对于所有 0 <= j < n - 1 都有 values[i][j] >= values[i][j + 1] 。
每一天，你可以在一个商店里购买一件物品。具体来说，在第 d 天，你可以：
- 选择商店
i。 - 购买数组中最右边的物品
j，开销为values[i][j] * d。换句话说，选择该商店中还没购买过的物品中最大的下标j，并且花费values[i][j] * d去购买。
注意，所有物品都视为不同的物品。比方说如果你已经从商店 1 购买了物品 0 ，你还可以在别的商店里购买其他商店的物品 0 。
请你返回购买所有 m * n 件物品需要的 最大开销 。
示例 1：
输入：values = [[8,5,2],[6,4,1],[9,7,3]] 输出：285 解释：第一天，从商店 1 购买物品 2 ，开销为 values[1][2] * 1 = 1 。 第二天，从商店 0 购买物品 2 ，开销为 values[0][2] * 2 = 4 。 第三天，从商店 2 购买物品 2 ，开销为 values[2][2] * 3 = 9 。 第四天，从商店 1 购买物品 1 ，开销为 values[1][1] * 4 = 16 。 第五天，从商店 0 购买物品 1 ，开销为 values[0][1] * 5 = 25 。 第六天，从商店 1 购买物品 0 ，开销为 values[1][0] * 6 = 36 。 第七天，从商店 2 购买物品 1 ，开销为 values[2][1] * 7 = 49 。 第八天，从商店 0 购买物品 0 ，开销为 values[0][0] * 8 = 64 。 第九天，从商店 2 购买物品 0 ，开销为 values[2][0] * 9 = 81 。 所以总开销为 285 。 285 是购买所有 m * n 件物品的最大总开销。
示例 2：
输入：values = [[10,8,6,4,2],[9,7,5,3,2]] 输出：386 解释：第一天，从商店 0 购买物品 4 ，开销为 values[0][4] * 1 = 2 。 第二天，从商店 1 购买物品 4 ，开销为 values[1][4] * 2 = 4 。 第三天，从商店 1 购买物品 3 ，开销为 values[1][3] * 3 = 9 。 第四天，从商店 0 购买物品 3 ，开销为 values[0][3] * 4 = 16 。 第五天，从商店 1 购买物品 2 ，开销为 values[1][2] * 5 = 25 。 第六天，从商店 0 购买物品 2 ，开销为 values[0][2] * 6 = 36 。 第七天，从商店 1 购买物品 1 ，开销为 values[1][1] * 7 = 49 。 第八天，从商店 0 购买物品 1 ，开销为 values[0][1] * 8 = 64 。 第九天，从商店 1 购买物品 0 ，开销为 values[1][0] * 9 = 81 。 第十天，从商店 0 购买物品 0 ，开销为 values[0][0] * 10 = 100 。 所以总开销为 386 。 386 是购买所有 m * n 件物品的最大总开销。
提示：
1 <= m == values.length <= 101 <= n == values[i].length <= 1041 <= values[i][j] <= 106values[i]按照非递增顺序排序。
解题思路
方法一：贪心 + 优先队列
根据题目描述，我们应该优先选择价值越小的物品，把价值越大的物品留到后面购买，这样才能使得总开销最大。因此，我们使用优先队列（小根堆）存储每个商店中还未购买的最小价值的物品。初始时，我们将每个商店中最右边的物品加入优先队列。
在每一天，我们从优先队列中取出价值最小的物品，将其加入答案，并将该物品所在商店中的上一个物品加入优先队列。我们重复上述操作，直到优先队列为空。
时间复杂度 ，空间复杂度 。其中 和 分别是数组 的行数和列数。
class Solution:
def maxSpending(self, values: List[List[int]]) -> int:
n = len(values[0])
pq = [(row[-1], i, n - 1) for i, row in enumerate(values)]
heapify(pq)
ans = d = 0
while pq:
d += 1
v, i, j = heappop(pq)
ans += v * d
if j:
heappush(pq, (values[i][j - 1], i, j - 1))
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity depends on the final approach. Using a priority queue for each shop leads to an overall time complexity of O(m * n log n), where m is the number of shops and n is the number of items per shop. Space complexity is also O(m * n) to store the heap structures for each shop. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Can the candidate apply greedy algorithms in a structured, problem-specific way?
- question_mark
Does the candidate efficiently utilize data structures like heaps or priority queues?
- question_mark
Can the candidate balance between greedy choice and maintaining invariant properties?
常见陷阱
外企场景- error
Selecting items without considering the day multiplier can lead to suboptimal solutions.
- error
Not maintaining the correct heap structure or failing to efficiently pop the maximum values from the heap.
- error
Ignoring the constraints that each item is unique across all shops, which may lead to confusion when selecting items.
进阶变体
外企场景- arrow_right_alt
What if the number of shops or items is much larger? Would the solution scale efficiently?
- arrow_right_alt
Can this problem be adapted to allow purchasing multiple items per day, or is it strictly one item per day?
- arrow_right_alt
How would the problem change if the values were sorted in increasing order instead of non-increasing order?