Medium

题目描述

你有一些不同颜色的球，有一个客户想要订购任意颜色的球。

客户对彩色球的估值很奇怪。每个彩色球的价值等于你目前库存中该颜色球的数量。例如，如果你拥有 6 个黄球，客户会为第一个黄球支付 6。交易后，只剩下 5 个黄球，所以下一个黄球的价值为 5（即球的价值随着你向客户出售更多球而递减）。

给你一个整数数组 inventory，其中 inventory[i] 表示第 i 种颜色的球的初始数量。还给你一个整数 orders，表示客户想要的球的总数。你可以按任何顺序出售球。

返回销售 orders 个彩球后能获得的最大总价值。由于答案可能很大，请返回对 10^9 + 7 取模的结果。

示例 1：

输入：inventory = [2,5], orders = 4
输出：14
解释：第1种颜色卖1次(2)，第2种颜色卖3次(5 + 4 + 3)。
最大总价值是 2 + 5 + 4 + 3 = 14。

示例 2：

输入：inventory = [3,5], orders = 6
输出：19
解释：第1种颜色卖2次(3 + 2)，第2种颜色卖4次(5 + 4 + 3 + 2)。
最大总价值是 3 + 2 + 5 + 4 + 3 + 2 = 19。

约束条件：

  • 1 <= inventory.length <= 10^5
  • 1 <= inventory[i] <= 10^9
  • 1 <= orders <= min(sum(inventory[i]), 10^9)

解题思路

这道题的核心思想是贪心策略：每次都卖出价值最高的球来获得最大收益。

解题思路分析：

  1. 贪心策略：由于我们想要最大化总价值，应该优先卖出当前价值最高的球。每卖出一个球，该颜色球的价值就会减1。

  2. 排序 + 模拟：可以对库存进行排序，然后模拟卖球的过程。但这种方法在数据量大时会超时。

  3. 二分查找优化（推荐）：关键观察是，必定存在一个阈值 k，使得所有价值大于 k 的球都会被完全卖出，价值等于 k 的球可能部分卖出。我们可以用二分查找找到这个 k 值。

  4. 数学计算：对于每个颜色，如果要从价值 high 卖到价值 low（包含），总价值为等差数列求和：(high + low) * count / 2。

算法流程：

  • 先对库存排序
  • 二分查找阈值 k
  • 计算所有价值 > k 的球的贡献（完全卖出）
  • 计算价值 = k 的球的贡献（部分卖出）

这种方法时间复杂度为 O(n log max(inventory))，空间复杂度为 O(1)。

代码实现

class Solution {
public:
    int maxProfit(vector<int>& inventory, int orders) {
        sort(inventory.begin(), inventory.end(), greater<int>());
        
        long long left = 0, right = *max_element(inventory.begin(), inventory.end());
        long long k = 0;
        
        while (left <= right) {
            long long mid = left + (right - left) / 2;
            long long count = 0;
            
            for (int inv : inventory) {
                if (inv > mid) {
                    count += inv - mid;
                }
            }
            
            if (count <= orders) {
                k = mid;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        
        long long result = 0;
        long long usedOrders = 0;
        const int MOD = 1e9 + 7;
        
        for (int inv : inventory) {
            if (inv > k) {
                long long count = inv - k;
                usedOrders += count;
                result = (result + ((long long)inv + k + 1) * count / 2) % MOD;
            }
        }
        
        long long remaining = orders - usedOrders;
        result = (result + remaining * k) % MOD;
        
        return (int)result;
    }
};

class Solution:
    def maxProfit(self, inventory: List[int], orders: int) -> int:
        inventory.sort(reverse=True)
        
        left, right = 0, max(inventory)
        k = 0
        
        while left <= right:
            mid = (left + right) // 2
            count = sum(max(0, inv - mid) for inv in inventory)
            
            if count <= orders:
                k = mid
                right = mid - 1
            else:
                left = mid + 1
        
        result = 0
        used_orders = 0
        MOD = 10**9 + 7
        
        for inv in inventory:
            if inv > k:
                count = inv - k
                used_orders += count
                result = (result + (inv + k + 1) * count // 2) % MOD
        
        remaining = orders - used_orders
        result = (result + remaining * k) % MOD
        
        return result

public class Solution {
    public int MaxProfit(int[] inventory, int orders) {
        Array.Sort(inventory, (a, b) => b.CompareTo(a));
        
        long left = 0, right = inventory.Max();
        long k = 0;
        
        while (left <= right) {
            long mid = left + (right - left) / 2;
            long count = 0;
            
            foreach (int inv in inventory) {
                if (inv > mid) {
                    count += inv - mid;
                }
            }
            
            if (count <= orders) {
                k = mid;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        
        long result = 0;
        long usedOrders = 0;
        const int MOD = 1000000007;
        
        foreach (int inv in inventory) {
            if (inv > k) {
                long count = inv - k;
                usedOrders += count;
                result = (result + (inv + k + 1) * count / 2) % MOD;
            }
        }
        
        long remaining = orders - usedOrders;
        result = (result + remaining * k) % MOD;
        
        return (int)result;
    }
}

/**
 * @param {number[]} inventory
 * @param {number} orders
 * @return {number}
 */
var maxProfit = function(inventory, orders) {
    inventory.sort((a, b) => b - a);
    
    let left = 0, right = Math.max(...inventory);
    let k = 0;
    
    while (left <= right) {
        let mid = Math.floor((left + right) / 2);
        let count = 0;
        
        for (let inv of inventory) {
            if (inv > mid) {
                count += inv - mid;
            }
        }
        
        if (count <= orders) {
            k = mid;
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    
    let result = 0;
    let usedOrders = 0;
    const MOD = 1e9 + 7;
    
    for (let inv of inventory) {
        if (inv > k) {
            let count = inv - k;
            usedOrders += count;
            result = (result + Math.floor((inv + k + 1) * count / 2)) % MOD;
        }
    }
    
    let remaining = orders - usedOrders;
    result = (result + remaining * k) % MOD;
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(n log max(inventory))，其中 n 是颜色数量。二分查找需要 O(log max(inventory)) 次，每次需要 O(n) 时间计算
空间复杂度O(1)，只使用常数额外空间（不考虑排序的空间）

相关题目