目标
给你一个下标从 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 <= 10
- 1 <= n == values[i].length <= 10^4
1 <= values[i][j] <= 10^6- values[i] 按照非递增顺序排序。
思路
有 m 个商店，每个商店里有 n 个商品。values[i][j] 表示商店 i 中商品 j 的价值，values[i] 非严格递减。从第一天开始，在第 d 天，我们可以选择一个商店 i，花费 d * values[i][j] 购买剩余的商品中价值中最小的商品 j。返回购买完所有商店的所有商品所需的最大开销。
要使开销最大，我们应该优先购买价值最小的商品，因为开销有天数加成，价值越大，在后面买翻倍后开销更大。由于每个商店里的商品是非严格递减的，每次从所有商店末尾取价值最小的商品，实际上就是按照所有商店的所有商品的价值从小到大取。
我们可以使用最小堆维护每个商店的最后一个商品，堆中元素记录商店编号 i，与商品下标 j。
如果是求最小开销呢？
如果没有限制购买规则，显然先购买高价值商品花费最小。但是题目规定每一次任选一个商店从其剩余商品中的最后一个（剩余商品中价值最低的）商品购买。
我们应该从 左边 开始优先购买价值 最小 的商品，然后将顺序 反转 就得到了从右购买的序列，按照这个顺序计算购买的开销。
注意：不能从右边选最大的买，比如：
100000 90000 1
100 10 2
如果从右边取最大的，购买顺序为 2 10 100 1 90000 100000，这显然不是最小开销。而从左边取最小的买，顺序为 100 10 2 100000 90000 1，反转得到 1 90000 100000 2 10 100 按此顺序购买花费最小。
代码
/**
* @date 2024-12-12 14:11
*/
public class MaxSpending2931 {
/**
* 13ms
* 直接合并为一维数组后排序
* 时间复杂度 O(mnlog(mn))
* 执行快是因为不用维护堆以及操作堆中数据的值，每次计算的复杂度小于维护数据结构的复杂度
*/
public long maxSpending_v2(int[][] values) {
int m = values.length;
int n = values[0].length;
long res = 0L;
long d = 1L;
int[] v = new int[m * n];
for (int i = 0; i < m; i++) {
System.arraycopy(values[i], 0, v, i * n, n);
}
Arrays.sort(v);
for (int i : v) {
res += d++ * i;
}
return res;
}
/**
* 37ms
* 时间复杂度 O(mnlog(m))
*/
public long maxSpending(int[][] values) {
int m = values.length;
int n = values[0].length;
PriorityQueue<int[]> q = new PriorityQueue<>(m, (a, b) -> a[0] - b[0]);
for (int i = 0; i < m; i++) {
q.offer(new int[]{values[i][n - 1], i, n - 1});
}
long res = 0L;
long d = 1L;
while (!q.isEmpty()) {
int[] goods = q.poll();
int storeIndex = goods[1];
res += d++ * goods[0];
int p = --goods[2];
if (p >= 0) {
q.offer(new int[]{values[storeIndex][p], storeIndex, p});
}
}
return res;
}
}
性能
