3814. 在预算内的最大容量

Medium

题目描述

给你两个长度为 n 的整数数组 costs 和 capacity，其中 costs[i] 表示第 i 台机器的购买成本，capacity[i] 表示其性能容量。

你还会得到一个整数 budget。

你最多可以选择两台不同的机器，使得所选机器的总成本严格小于 budget。

返回所选机器的最大可达到总容量。

示例 1：

输入：costs = [4,8,5,3], capacity = [1,5,2,7], budget = 8
输出：8
解释：
选择两台机器，costs[0] = 4 和 costs[3] = 3。
总成本是 4 + 3 = 7，严格小于 budget = 8。
最大总容量是 capacity[0] + capacity[3] = 1 + 7 = 8。

示例 2：

输入：costs = [3,5,7,4], capacity = [2,4,3,6], budget = 7
输出：6
解释：
选择一台机器，costs[3] = 4。
总成本是 4，严格小于 budget = 7。
最大总容量是 capacity[3] = 6。

示例 3：

输入：costs = [2,2,2], capacity = [3,5,4], budget = 5
输出：9
解释：
选择两台机器，costs[1] = 2 和 costs[2] = 2。
总成本是 2 + 2 = 4，严格小于 budget = 5。
最大总容量是 capacity[1] + capacity[2] = 5 + 4 = 9。

约束条件：

1 <= n == costs.length == capacity.length <= 10^5
1 <= costs[i], capacity[i] <= 10^5
1 <= budget <= 2 * 10^5

解题思路

这道题目要求在预算范围内选择最多两台机器，使得总容量最大。我们需要考虑两种情况：选择一台机器和选择两台机器。

核心思路：

预处理排序：将机器按照成本从小到大排序，同时保持容量对齐。这样可以方便我们进行二分搜索。
构建前缀最大值数组：创建 prefMax[i] 数组，存储索引 <= i 的所有机器中的最大容量。这样可以快速查询某个成本范围内的最大容量。
单机器情况：遍历所有成本小于预算的机器，找到容量最大的一台。
双机器情况：对于每台机器 i，使用二分搜索找到最大的索引 j < i，使得 costs[j] < budget - costs[i]。如果找到这样的 j，则更新答案为 capacity[i] + prefMax[j]。
优化技巧：通过排序和前缀最大值数组，我们可以在 O(log n) 时间内找到任意成本限制下的最大容量，总体时间复杂度为 O(n log n)。

这种方法既考虑了单机器的最优选择，也通过二分搜索高效地处理了双机器的组合优化问题。

代码实现

class Solution {
public:
    int maxCapacity(vector<int>& costs, vector<int>& capacity, int budget) {
        int n = costs.size();
        vector<pair<int, int>> machines(n);
        
        for (int i = 0; i < n; i++) {
            machines[i] = {costs[i], capacity[i]};
        }
        
        sort(machines.begin(), machines.end());
        
        vector<int> prefMax(n);
        prefMax[0] = machines[0].second;
        for (int i = 1; i < n; i++) {
            prefMax[i] = max(prefMax[i-1], machines[i].second);
        }
        
        int maxCap = 0;
        
        // Single machine
        for (int i = 0; i < n; i++) {
            if (machines[i].first < budget) {
                maxCap = max(maxCap, machines[i].second);
            }
        }
        
        // Two machines
        for (int i = 0; i < n; i++) {
            int remainBudget = budget - machines[i].first;
            if (remainBudget <= 0) break;
            
            // Binary search for largest j < i with machines[j].first < remainBudget
            int left = 0, right = i - 1, j = -1;
            while (left <= right) {
                int mid = left + (right - left) / 2;
                if (machines[mid].first < remainBudget) {
                    j = mid;
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }
            
            if (j != -1) {
                maxCap = max(maxCap, machines[i].second + prefMax[j]);
            }
        }
        
        return maxCap;
    }
};

class Solution:
    def maxCapacity(self, costs: List[int], capacity: List[int], budget: int) -> int:
        n = len(costs)
        machines = list(zip(costs, capacity))
        machines.sort()
        
        pref_max = [0] * n
        pref_max[0] = machines[0][1]
        for i in range(1, n):
            pref_max[i] = max(pref_max[i-1], machines[i][1])
        
        max_cap = 0
        
        # Single machine
        for cost, cap in machines:
            if cost < budget:
                max_cap = max(max_cap, cap)
        
        # Two machines
        for i in range(n):
            remain_budget = budget - machines[i][0]
            if remain_budget <= 0:
                break
            
            # Binary search for largest j < i with machines[j][0] < remain_budget
            left, right, j = 0, i - 1, -1
            while left <= right:
                mid = (left + right) // 2
                if machines[mid][0] < remain_budget:
                    j = mid
                    left = mid + 1
                else:
                    right = mid - 1
            
            if j != -1:
                max_cap = max(max_cap, machines[i][1] + pref_max[j])
        
        return max_cap

public class Solution {
    public int MaxCapacity(int[] costs, int[] capacity, int budget) {
        int n = costs.Length;
        var machines = new (int cost, int capacity)[n];
        
        for (int i = 0; i < n; i++) {
            machines[i] = (costs[i], capacity[i]);
        }
        
        Array.Sort(machines, (a, b) => a.cost.CompareTo(b.cost));
        
        int[] prefMax = new int[n];
        prefMax[0] = machines[0].capacity;
        for (int i = 1; i < n; i++) {
            prefMax[i] = Math.Max(prefMax[i-1], machines[i].capacity);
        }
        
        int maxCap = 0;
        
        // Single machine
        for (int i = 0; i < n; i++) {
            if (machines[i].cost < budget) {
                maxCap = Math.Max(maxCap, machines[i].capacity);
            }
        }
        
        // Two machines
        for (int i = 0; i < n; i++) {
            int remainBudget = budget - machines[i].cost;
            if (remainBudget <= 0) break;
            
            // Binary search for largest j < i with machines[j].cost < remainBudget
            int left = 0, right = i - 1, j = -1;
            while (left <= right) {
                int mid = left + (right - left) / 2;
                if (machines[mid].cost < remainBudget) {
                    j = mid;
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }
            
            if (j != -1) {
                maxCap = Math.Max(maxCap, machines[i].capacity + prefMax[j]);
            }
        }
        
        return maxCap;
    }
}

var maxCapacity = function(costs, capacity, budget) {
    const n = costs.length;
    const machines = [];
    
    for (let i = 0; i < n; i++) {
        machines.push([costs[i], capacity[i]]);
    }
    
    machines.sort((a, b) => a[0] - b[0]);
    
    const prefMax = new Array(n);
    prefMax[0] = machines[0][1];
    for (let i = 1; i < n; i++) {
        prefMax[i] = Math.max(prefMax[i-1], machines[i][1]);
    }
    
    let maxCap = 0;
    
    // Single machine
    for (let i = 0; i < n; i++) {
        if (machines[i][0] < budget) {
            maxCap = Math.max(maxCap, machines[i][1]);
        }
    }
    
    // Two machines
    for (let i = 0; i < n; i++) {
        const remainBudget = budget - machines[i][0];
        if (remainBudget <= 0) break;
        
        // Binary search for largest j < i with machines[j][0] < remainBudget
        let left = 0, right = i - 1, j = -1;
        while (left <= right) {
            const mid = Math.floor((left + right) / 2);
            if (machines[mid][0] < remainBudget) {
                j = mid;
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        
        if (j !== -1) {
            maxCap = Math.max(maxCap, machines[i][1] + prefMax[j]);
        }
    }
    
    return maxCap;
};

在 LeetCode 上运行：力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型	复杂度	说明
时间复杂度	O(n log n)	排序需要 O(n log n)，每次二分搜索需要 O(log n)，总共进行 n 次搜索
空间复杂度	O(n)	需要额外的数组存储排序后的机器信息和前缀最大值数组

题目描述#

解题思路#

代码实现#

复杂度分析#

题目描述

解题思路

代码实现

复杂度分析