2931.购买物品的最大开销

【LetMeFly】2931.购买物品的最大开销：多指针（平均优于排序）

力扣题目链接：https://leetcode.cn/problems/maximum-spending-after-buying-items/

给你一个下标从 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 <= 104
  • 1 <= values[i][j] <= 106
  • values[i] 按照非递增顺序排序。

解题方法：多指针

首先需要明确，最佳购买顺序是：将所有商店的所有商品从小到大排序，之后依次购买。

首先购买越晚系数越大，所以贵的应该尽可能晚购买；

其次，一定可以做到按所有商品价值从小到大购买，因为越靠后的商品越便宜，当前最便宜的商品一定在最后面。

直接调用库函数排序就没有利用“每个商家的商品非递增”这一特性，且排序复杂度$mn\log (mn)$ 平均大于 $mn\times m$。

$ m $ $mn\log (mn)\gt mn\times m$
1 $ n \geq 3 $
2 $ n \geq 5 $
3 $ n \geq 9 $
4 $ n \geq 17 $
5 $ n \geq 33 $
6 $ n \geq 65 $
7 $ n \geq 129 $
8 $ n \geq 257 $
9 $ n \geq 513 $
10 $ n \geq 1025 $

因此，我们可以使用$m$个指针，每个指针指向这家商店购买到了哪件商品，每次从$m$家里选择最便宜的那件就好。

  • 时间复杂度$O(m^2n)$：单次选择复杂度$O(m)$，共选择$mn$次。$m$的最大范围比较小，最多为$10$。
  • 空间复杂度$O(m)$

AC代码

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
typedef long long ll;
class Solution {
public:
    ll maxSpending(vector<vector<int>>& values) {
        vector<int> loc(values.size(), values[0].size() - 1);
        ll ans = 0;
        int cnt = values.size() * values[0].size();
        ll th = 1;
        while (cnt--) {
            int m = 1e7, mLoc;
            for (int i = 0; i < values.size(); i++) {
                if (loc[i] >= 0 && values[i][loc[i]] < m) {
                    m = values[i][loc[i]];
                    mLoc = i;
                }
            }
            ans += values[mLoc][loc[mLoc]] * th;
            th++, loc[mLoc]--;
        }
        return ans;
    }
};

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
from typing import List

class Solution:
    def maxSpending(self, values: List[List[int]]) -> int:
        loc = [len(values[0]) - 1] * len(values)
        ans, cnt, th = 0, len(values) * len(values[0]), 1
        while th <= cnt:
            m, mLoc = 10000000, 0
            for i in range(len(values)):
                if loc[i] >= 0 and values[i][loc[i]] < m:
                    m, mLoc = values[i][loc[i]], i
            ans += th * values[mLoc][loc[mLoc]]
            th += 1
            loc[mLoc] -= 1
        return ans

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
import java.util.Arrays;

class Solution {
    public long maxSpending(int[][] values) {
        int[] loc = new int[values.length];
        Arrays.fill(loc, values[0].length - 1);
        long ans = 0, th = 1;
        int cnt = values.length * values[0].length;
        while (th <= cnt) {
            int m = 100000000, mLoc = 0;
            for (int i = 0; i < values.length; i++) {
                if (loc[i] >= 0 && values[i][loc[i]] < m) {
                    m = values[i][loc[i]];
                    mLoc = i;
                }
            }
            ans += values[mLoc][loc[mLoc]] * th;
            th++;
            loc[mLoc]--;
        }
        return ans;
    }
}

Go

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
package main

func maxSpending(values [][]int) (ans int64) {
    loc := make([]int, len(values))
    for i := range loc {
        loc[i] = len(values[0]) - 1
    }
    cnt, th := (int64)(len(values) * len(values[0])), (int64)(1)
    for th <= cnt {
        m, mLoc := 10000000, 0
        for i := range values {
            if loc[i] >= 0 && values[i][loc[i]] < m {
                m, mLoc = values[i][loc[i]], i
            }
        }
        ans += (int64)(values[mLoc][loc[mLoc]]) * th
        th++
        loc[mLoc]--
    }
    return
}

同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~

Tisfy：https://letmefly.blog.csdn.net/article/details/144428274

#题解 #数组 #贪心 #排序 #LeetCode #困难 #堆（优先队列） #矩阵 #多指针
2931.购买物品的最大开销
https://blog.letmefly.xyz/2024/12/12/LeetCode 2931.购买物品的最大开销/
作者
Tisfy
发布于
2024年12月12日
许可协议