Hard

题目描述

给你一个下标从 0 开始的 m x n 整数矩阵 values，表示 m 个不同商店里 m x n 个不同物品的价值。每个商店有 n 个物品，第 i 个商店的第 j 个物品的价值为 values[i][j]。此外，第 i 个商店的物品已经按照价值非递增的顺序排好序了，也就是说 values[i][j] >= values[i][j + 1] 对于所有 0 <= j < n - 1 都成立。

每一天，你可以在一个商店里购买一件物品。具体来说，在第 d 天，你可以：

  • 选择任意一个商店 i
  • 购买数组中最右边的物品 j ，开销为 values[i][j] * d。换句话说，选择该商店中下标最大的物品 j ，该物品没有被购买过，以 values[i][j] * d 的价格购买

注意，所有物品都视为不同的物品。如果你已经从商店 1 购买了物品 0，你还可以在别的商店购买其他的物品 0。

返回购买所有 m x 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

示例 2：

输入：values = [[10,8,6,4,2],[9,7,5,3,2]]
输出：386

提示：

  • 1 <= m == values.length <= 10
  • 1 <= n == values[i].length <= 10^4
  • 1 <= values[i][j] <= 10^6
  • values[i] 已经按非递增顺序排序

解题思路

解题思路

这道题的核心是要最大化总开销，而每天的开销为物品价值乘以天数。由于天数是递增的，我们需要合理安排购买顺序。

关键观察：

  1. 每天购买的开销 = 物品价值 × 当前天数
  2. 天数越大，同样价值的物品开销越高
  3. 要最大化总开销，应该让价值大的物品在后面的天数购买

贪心策略： 每天都选择当前所有商店中最右边物品值最小的那个物品购买。这样可以确保价值大的物品留到后面天数更大的时候购买，从而最大化总开销。

算法步骤：

  1. 使用最小堆维护每个商店当前最右边物品的值和对应的商店索引
  2. 每天从堆中取出最小值对应的物品购买
  3. 购买后将该商店的指针左移，如果还有物品则重新入堆
  4. 重复直到所有物品都被购买

推荐解法： 使用优先队列（最小堆）的贪心算法，时间复杂度最优且实现简洁。

另一种解法是将所有物品排序后按价值从小到大购买，但需要额外的空间存储所有物品。

代码实现

class Solution {
public:
    long long maxSpending(vector<vector<int>>& values) {
        int m = values.size(), n = values[0].size();
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
        
        vector<int> pos(m, n - 1);
        
        for (int i = 0; i < m; i++) {
            pq.push({values[i][pos[i]], i});
        }
        
        long long result = 0;
        int day = 1;
        
        while (!pq.empty()) {
            auto [val, shop] = pq.top();
            pq.pop();
            
            result += (long long)val * day;
            day++;
            
            pos[shop]--;
            if (pos[shop] >= 0) {
                pq.push({values[shop][pos[shop]], shop});
            }
        }
        
        return result;
    }
};

class Solution:
    def maxSpending(self, values: List[List[int]]) -> int:
        import heapq
        
        m, n = len(values), len(values[0])
        heap = []
        pos = [n - 1] * m
        
        for i in range(m):
            heapq.heappush(heap, (values[i][pos[i]], i))
        
        result = 0
        day = 1
        
        while heap:
            val, shop = heapq.heappop(heap)
            result += val * day
            day += 1
            
            pos[shop] -= 1
            if pos[shop] >= 0:
                heapq.heappush(heap, (values[shop][pos[shop]], shop))
        
        return result

public class Solution {
    public long MaxSpending(int[][] values) {
        int m = values.Length, n = values[0].Length;
        var pq = new PriorityQueue<(int val, int shop), int>();
        int[] pos = new int[m];
        
        for (int i = 0; i < m; i++) {
            pos[i] = n - 1;
            pq.Enqueue((values[i][pos[i]], i), values[i][pos[i]]);
        }
        
        long result = 0;
        int day = 1;
        
        while (pq.Count > 0) {
            var (val, shop) = pq.Dequeue();
            result += (long)val * day;
            day++;
            
            pos[shop]--;
            if (pos[shop] >= 0) {
                pq.Enqueue((values[shop][pos[shop]], shop), values[shop][pos[shop]]);
            }
        }
        
        return result;
    }
}

var maxSpending = function(values) {
    const m = values.length, n = values[0].length;
    const heap = new MinPriorityQueue({priority: x => x[0]});
    const pos = new Array(m).fill(n - 1);
    
    for (let i = 0; i < m; i++) {
        heap.enqueue([values[i][pos[i]], i]);
    }
    
    let result = 0;
    let day = 1;
    
    while (!heap.isEmpty()) {
        const [val, shop] = heap.dequeue().element;
        result += val * day;
        day++;
        
        pos[shop]--;
        if (pos[shop] >= 0) {
            heap.enqueue([values[shop][pos[shop]], shop]);
        }
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

解法时间复杂度空间复杂度
优先队列贪心O(mn log m)O(m)
排序后贪心O(mn log(mn))O(mn)

说明：

  • 时间复杂度：每个物品都要进出堆一次，每次操作的复杂度为 O(log m)
  • 空间复杂度：堆中最多存储 m 个元素，pos 数组需要 O(m) 空间

相关题目