千问 LeetCode 2931. 购买物品的最大开销 Java实现

这道题是一道经典的贪心算法题目结合了多路归并的思想。 核心解题思路1. 贪心策略题目要求总开销最大而总开销的计算公式是 物品价值 * 购买天数。为了让总和最大我们需要让价值越大的物品在越靠后的天数即更大的天数系数购买而价值越小的物品在越靠前的天数购买。2. 购买规则题目规定每天只能购买某个商店中最右边即当前剩余物品中价值最小的物品且每个商店的物品已经按非递增从大到小排好序。这意味着我们每天能买到的候选物品就是所有商店当前最右侧的那一个。3. 算法转化为了每天都买到当前所有候选物品中价值最小的那个我们需要在每一轮每一天从所有商店的最右侧物品中挑出最小值。这本质上是一个 m 路归并的问题非常适合使用最小堆优先队列来高效解决。 Java 代码实现import java.util.PriorityQueue;class Solution {public long maxSpending(int[][] values) {int m values.length;int n values[0].length;// 最小堆存储的是 int[]{商店下标, 物品下标}// 按照物品的实际价值 values[i][j] 从小到大排序PriorityQueueint[] minHeap new PriorityQueue((a, b) -values[a[0]][a[1]] - values[b[0]][b[1]]);// 1. 初始化将每个商店最右侧价值最小的物品下标加入堆中for (int i 0; i m; i) {minHeap.offer(new int[]{i, n - 1});}long maxSpending 0;// 2. 模拟每一天从第1天到第 m*n 天for (int day 1; day m * n; day) {// 弹出当前所有候选物品中价值最小的那个int[] current minHeap.poll();int shopIdx current[0];int itemIdx current[1];// 累加开销当前物品价值 * 当前天数maxSpending (long) values[shopIdx][itemIdx] * day;// 3. 如果该商店还有左边的物品将其加入堆中作为下一轮的候选if (itemIdx 0) {minHeap.offer(new int[]{shopIdx, itemIdx - 1});}}return maxSpending;}} 复杂度分析* 时间复杂度O(mn log m)。我们需要进行 m*n 次循环购买所有物品每次循环中堆的弹出和插入操作的时间复杂度是 O(log m)因为堆中最多同时存在 m 个商店的候选物品。* 空间复杂度O(m)。优先队列最小堆中最多同时存储 m 个元素。⚠️ 易错点提示1. 数据溢出题目中物品价值和天数的乘积可能会非常大极易超出 int 的范围。因此累加开销的变量 maxSpending 以及乘法运算时必须强制转换为 long 类型例如 (long) values[shopIdx][itemIdx] * day。2. 贪心证明核心在于理解“便宜的先买贵的后买”这一贪心原则。根据排序不等式两个同向序列的乘积和最大因此将升序排列的物品价值与升序排列的天数1, 2, 3...一一对应相乘即可得到最大开销。