面试算法优化求助：贪心店主最大收益问题超时解决方案

给定多种商品的库存数组，需要进行m次销售：每次选择当前库存最大的商品卖出一件，售价等于当前库存数，卖出后该商品库存减1。目标是计算最大收益，要求Java实现能处理1e5量级的商品种类、单种库存和销售次数，且在4秒内完成。

示例：库存数组[10,10,8,9,1]，6次销售的最大收益为10+10+9+9+9+8=55。

你的尝试超时原因分析 #

• 每次调用Collections.max和indexOf都是O(n)时间复杂度，m次循环总复杂度为O(mn)，1e5量级下会产生1e10次操作，完全超出时间限制。
• 每次排序取顶部元素，总复杂度O(mn log n)，效率更低。
• 排序后插入保持有序，每次插入操作是O(n)，总时间仍为O(mn)，无法通过。
• 相邻比较找最大值逻辑错误，无法保证每次取到全局最大值，结果不准确。

优化方案 #

方案一：最大优先队列（Max-Heap） #

利用Java的PriorityQueue实现最大堆，每次快速获取当前最大库存值，处理后将减1的值放回堆中，大幅降低单次操作的时间复杂度。

时间复杂度

• 初始化堆：O(n log n)
• m次销售操作：每次堆顶弹出和插入都是O(log n)，总时间O(m log n)
• 整体复杂度O(n log n + m log n)，完全满足1e5量级数据的时间要求。

Java代码实现

import java.util.Collections;
import java.util.List;
import java.util.PriorityQueue;

public class GreedyShopkeeper {
    public static long getMaximumAmount(List<Integer> arr, int m) {
        // 初始化最大堆
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
        maxHeap.addAll(arr);
        
        long revenue = 0;
        while (m > 0) {
            int currentMax = maxHeap.poll();
            revenue += currentMax;
            // 剩余库存大于0时放回堆中
            if (currentMax > 1) {
                maxHeap.offer(currentMax - 1);
            }
            m--;
        }
        return revenue;
    }
}

方案二：批量数学计算（更高效） #

当m很大时，堆的单次操作仍有开销，通过排序后批量计算连续相同或递减的收益，可大幅减少循环次数，进一步提升性能。

思路

1. 将库存数组按降序排序。
2. 遍历数组，维护当前最高库存值current和连续拥有该库存的商品数量count。
3. 计算可批量销售的次数：batch = Math.min(m, count * (current - nextVal))（nextVal为下一个库存值，无后续元素则为0）。
4. 按等差数列求和公式计算该批量的收益，避免逐次累加。
5. 更新剩余销售次数m，直到m为0。

时间复杂度

• 排序：O(n log n)
• 批量计算：O(n)，每个元素最多处理一次
• 整体复杂度O(n log n)，性能优于堆方案，尤其适合m接近总库存的场景。

Java代码实现

import java.util.Collections;
import java.util.List;

public class GreedyShopkeeper {
    public static long getMaximumAmount(List<Integer> arr, int m) {
        Collections.sort(arr, Collections.reverseOrder());
        long revenue = 0;
        int n = arr.size();
        int i = 0;
        
        while (m > 0 && i < n) {
            int current = arr.get(i);
            // 统计连续等于current的商品数量
            int count = 0;
            while (i < n && arr.get(i) == current) {
                count++;
                i++;
            }
            // 获取下一个库存值，无则为0
            int nextVal = (i < n) ? arr.get(i) : 0;
            // 计算当前可批量销售的最大次数
            int maxPossibleBatch = count * (current - nextVal);
            int batch = Math.min(m, maxPossibleBatch);
            
            if (batch == 0) break;
            
            // 计算批量收益
            int fullCycles = batch / count;
            int remainder = batch % count;
            // 完整循环的收益（等差数列求和）
            if (fullCycles > 0) {
                long sumPerCycle = (long) current + (current - fullCycles + 1);
                sumPerCycle *= fullCycles;
                sumPerCycle /= 2;
                revenue += sumPerCycle * count;
            }
            // 剩余单次销售的收益
            if (remainder > 0) {
                revenue += (long) (current - fullCycles) * remainder;
            }
            
            m -= batch;
        }
        
        return revenue;
    }
}

方案对比 #

• 堆方案：实现简单直观，代码易维护，适合m较小的场景。
• 批量计算方案：性能更优，尤其是当m接近总库存时，能大幅减少循环次数，适合大数据量的极限场景。

内容的提问来源于stack exchange，提问作者user3525805