leetcode
leetcode 2451 ~ 2500
购买物品的最大开销

购买物品的最大开销

难度:

标签:

题目描述

You are given a 0-indexed m * n integer matrix values, representing the values of m * n different items in m different shops. Each shop has n items where the jth item in the ith shop has a value of values[i][j]. Additionally, the items in the ith shop are sorted in non-increasing order of value. That is, values[i][j] >= values[i][j + 1] for all 0 <= j < n - 1.

On each day, you would like to buy a single item from one of the shops. Specifically, On the dth day you can:

  • Pick any shop i.
  • Buy the rightmost available item j for the price of values[i][j] * d. That is, find the greatest index j such that item j was never bought before, and buy it for the price of values[i][j] * d.

Note that all items are pairwise different. For example, if you have bought item 0 from shop 1, you can still buy item 0 from any other shop.

Return the maximum amount of money that can be spent on buying all m * n products.

 

Example 1:

Input: values = [[8,5,2],[6,4,1],[9,7,3]]
Output: 285
Explanation: On the first day, we buy product 2 from shop 1 for a price of values[1][2] * 1 = 1.
On the second day, we buy product 2 from shop 0 for a price of values[0][2] * 2 = 4.
On the third day, we buy product 2 from shop 2 for a price of values[2][2] * 3 = 9.
On the fourth day, we buy product 1 from shop 1 for a price of values[1][1] * 4 = 16.
On the fifth day, we buy product 1 from shop 0 for a price of values[0][1] * 5 = 25.
On the sixth day, we buy product 0 from shop 1 for a price of values[1][0] * 6 = 36.
On the seventh day, we buy product 1 from shop 2 for a price of values[2][1] * 7 = 49.
On the eighth day, we buy product 0 from shop 0 for a price of values[0][0] * 8 = 64.
On the ninth day, we buy product 0 from shop 2 for a price of values[2][0] * 9 = 81.
Hence, our total spending is equal to 285.
It can be shown that 285 is the maximum amount of money that can be spent buying all m * n products.

Example 2:

Input: values = [[10,8,6,4,2],[9,7,5,3,2]]
Output: 386
Explanation: On the first day, we buy product 4 from shop 0 for a price of values[0][4] * 1 = 2.
On the second day, we buy product 4 from shop 1 for a price of values[1][4] * 2 = 4.
On the third day, we buy product 3 from shop 1 for a price of values[1][3] * 3 = 9.
On the fourth day, we buy product 3 from shop 0 for a price of values[0][3] * 4 = 16.
On the fifth day, we buy product 2 from shop 1 for a price of values[1][2] * 5 = 25.
On the sixth day, we buy product 2 from shop 0 for a price of values[0][2] * 6 = 36.
On the seventh day, we buy product 1 from shop 1 for a price of values[1][1] * 7 = 49.
On the eighth day, we buy product 1 from shop 0 for a price of values[0][1] * 8 = 64
On the ninth day, we buy product 0 from shop 1 for a price of values[1][0] * 9 = 81.
On the tenth day, we buy product 0 from shop 0 for a price of values[0][0] * 10 = 100.
Hence, our total spending is equal to 386.
It can be shown that 386 is the maximum amount of money that can be spent buying all m * n products.

 

Constraints:

  • 1 <= m == values.length <= 10
  • 1 <= n == values[i].length <= 104
  • 1 <= values[i][j] <= 106
  • values[i] are sorted in non-increasing order.

代码结果

运行时间: 95 ms, 内存: 30.3 MB

/*
 * Problem: Similar to the above, we aim to maximize the total expense using Java Streams.
 * Approach:
 * 1. Flatten the matrix into a list of all values.
 * 2. Use Java Streams to sort and calculate the total expense.
 */
import java.util.*;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

public class MaxExpenseStream {
    public static int maxExpense(int[][] values) {
        List<Integer> sortedItems = Arrays.stream(values)
                .flatMapToInt(Arrays::stream)
                .boxed()
                .sorted(Collections.reverseOrder())
                .collect(Collectors.toList());

        return IntStream.range(0, sortedItems.size())
                .map(i -> sortedItems.get(i) * (i + 1))
                .sum();
    }

    public static void main(String[] args) {
        int[][] values = {{8, 5, 2}, {6, 4, 1}, {9, 7, 3}};
        System.out.println(maxExpense(values)); // Output: 285
    }
}

解释

方法:

这道题目的核心思想是将所有物品的价格从高到低排序，然后按照这个顺序依次购买，每次购买时的开销为物品价格乘以天数（从1开始）。这样做可以保证每次购买时都能获得最大的开销，因为价格较高的物品会在天数较大时购买，从而获得更大的开销。

时间复杂度:

O((m*n)log(m*n))

空间复杂度:

O(m*n)

代码细节讲解

🦆
在题解中，为什么选择将所有物品价格做平坦处理并排序来求解，而不是直接在每个商店内部选择最大价值的物品进行计算？
▷
将所有物品价格平坦处理并排序的原因是，这样可以确保我们总是能将最高的价格与最高的天数相乘，从而获得最大的开销。如果只在每个商店内部选择最大价值的物品，可能无法实现跨商店的最优价格组合，因为可能会错过其他商店中较高价值的物品。通过全局排序，我们可以确保每一天购买的都是当前可选物品中的最高价值物品。
🦆
排序所有物品的价格是否考虑了每个商店物品价值已经是非递增顺序的特性，这个特性是否可以用来优化算法？
▷
题解中的排序方法没有直接考虑每个商店物品已经是非递增顺序的特性。如果确实每个商店的物品价值是非递增的，我们可以考虑使用更复杂的优先级队列（如最大堆）来进行优化。这样可以在不完全排序的情况下，动态地选择当前所有商店中价值最高的物品，可能会在某些情况下减少排序的成本。
🦆
题解中提到按照价格高低顺序购买物品，但是实际上物品的价格与天数的乘积才是开销。请问如何保证这种排序方式是最优的？
▷
这种排序方式之所以是最优的，是基于一个贪心策略的思考：较高的价格应该尽可能与较高的天数相乘，以获取最大的开销。这是因为乘积的增长是线性的，即价格与天数的乘积总和是最大化开销的关键。通过将价格从高到低排序，确保每一天都能用最高可能的价格乘以当前的天数，从而达到全局最大开销。
🦆
在计算总开销的时候，为什么选择从1开始计数天数，这样的计数方式对结果有何影响？
▷
从1开始计数天数是因为第一天的购买也应该产生开销，且每过一天，天数的计数应增加1，以反映增长的时间成本。如果从0开始计数，则第一天的购买开销将为0，这不符合实际情况，因为即使是第一天，购买任何物品也应有相应的成本。开始计数天数为1能确保计算的开销与时间成本正确关联，反映真实情况。

相关问题

和为目标值的最长子序列的长度给定数字乘积的最小数字