[LeetCode] 每日一题 2931. 购买物品的最大开销

题目链接

题目描述

给你一个下标从 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] 按照非递增顺序排序。

题解

解题思路

• 每天可以从一个商店购买最右边的物品，开销与天数成正比。

• 为了最大化总开销，应尽可能将大的物品价值分配到较大的天数上。

因此，一个有效的策略是：将所有物品的价值排序，从最大的价值开始依次分配到最大的天数上。

解法步骤

1. 合并所有商店的物品价值：将 values 矩阵展平成一个一维数组，方便排序和计算。

2. 排序物品价值：将一维数组中的物品价值从小到大排序。

3. 计算最大开销：

   • 使用排序后的数组，从后向前遍历。

   • 每次取出最大的物品价值，并乘以对应的天数（从大到小的索引+1）。

4. 返回结果。

代码实现

class Solution {
    public long maxSpending(int[][] values) {
        int m = values.length; // 商店数量
        int n = values[0].length; // 每个商店的物品数量
        int[] a = new int[m * n]; // 展平后的物品数组

        // 合并所有商店的物品到一个数组中
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                a[j + i * n] = values[i][j];
            }
        }

        // 排序物品价值
        Arrays.sort(a);

        long ans = 0;
        int len = a.length;

        // 从后向前计算总开销
        for (int i = 0; i < len; i++) {
            ans += (long) a[len - 1 - i] * (i + 1);
        }

        return ans;
    }
}

复杂度分析

• 展平矩阵：时间复杂度为 O(m \times n)。

• 排序：时间复杂度为 O((m \times n) \log (m \times n))。

• 计算开销：时间复杂度为 O(m \times n)。

总时间复杂度为 O((m \times n) \log (m \times n))。

总结

• 贪心思想：通过排序让较大的价值分配到较大的天数，最大化结果。

• 矩阵展平技巧：使用一维数组存储所有物品价值，方便后续排序和操作。

• 时间复杂度优化：排序是关键，其他操作的复杂度较低。

希望这篇分享能为你带来启发！如果你有任何问题或建议，欢迎在评论区留言，与我共同交流探讨。