Medium

题目描述

给你两个下标从 0 开始的整数数组 nums1 和 nums2，两者长度都是 n，再给你一个正整数 k。你必须从 nums1 中选择长度为 k 的子序列对应的下标。

对于选择的下标 i0, i1, …, ik - 1，你的分数定义为：

  • 从 nums1 中选择的元素总和，乘以从 nums2 中选择的元素的最小值。
  • 简单来说就是：(nums1[i0] + nums1[i1] +...+ nums1[ik - 1]) * min(nums2[i0], nums2[i1], ..., nums2[ik - 1])。

请你返回 最大 可能的分数。

一个数组的 子序列 下标是集合 {0, 1, ..., n-1} 中删除若干元素得到的剩余集合，也可以不删除任何元素。

示例 1：

输入：nums1 = [1,3,3,2], nums2 = [2,1,3,4], k = 3
输出：12
解释：
四个可能的子序列分数为：
- 选择下标 0, 1, 2，分数为 (1+3+3) * min(2,1,3) = 7
- 选择下标 0, 1, 3，分数为 (1+3+2) * min(2,1,4) = 6
- 选择下标 0, 2, 3，分数为 (1+3+2) * min(2,3,4) = 12
- 选择下标 1, 2, 3，分数为 (3+3+2) * min(1,3,4) = 8
所以最大分数为 12 。

示例 2：

输入：nums1 = [4,2,3,1,1], nums2 = [7,5,10,9,6], k = 1
输出：30
解释：
选择下标 2 最优：nums1[2] * nums2[2] = 3 * 10 = 30 是可能的最大分数。

提示：

  • n == nums1.length == nums2.length
  • 1 <= n <= 10^5
  • 0 <= nums1[i], nums2[j] <= 10^5
  • 1 <= k <= n

解题思路

解题思路

这道题要求从数组中选择 k 个元素，使得 nums1 对应元素的和乘以 nums2 对应元素的最小值最大。

关键观察：分数公式中有一个最小值因子，这提示我们可以枚举这个最小值。如果我们能确定最小值，那么问题就转化为：在保证 nums2 中所选元素都不小于这个最小值的前提下，选择 nums1 中对应的 k 个最大元素。

算法步骤：

  1. 排序：将所有 (nums1[i], nums2[i]) 按 nums2[i] 降序排列。这样我们可以从大到小枚举可能的最小值。

  2. 枚举最小值：遍历排序后的数组，每次将当前 nums2[i] 作为可能的最小值。由于数组已按 nums2 降序排列，当我们考虑 nums2[i] 为最小值时，前面所有元素的 nums2 值都不小于它。

  3. 维护最大的 k 个 nums1 值：使用最小堆来维护当前考虑范围内 nums1 的最大 k 个值。每次添加新元素时，如果堆大小超过 k，就移除最小元素。

  4. 更新答案：当堆中有 k 个元素时，计算当前分数并更新最大值。

这个方法的巧妙之处在于：通过排序，我们确保了在考虑某个 nums2[i] 为最小值时，所有可选的元素都满足 nums2 值不小于它的条件。

推荐解法：排序 + 最小堆，时间复杂度 O(n log n)，空间复杂度 O(n)。

代码实现

class Solution {
public:
    long long maxScore(vector<int>& nums1, vector<int>& nums2, int k) {
        int n = nums1.size();
        vector<pair<int, int>> pairs;
        
        for (int i = 0; i < n; i++) {
            pairs.push_back({nums1[i], nums2[i]});
        }
        
        sort(pairs.begin(), pairs.end(), [](const pair<int, int>& a, const pair<int, int>& b) {
            return a.second > b.second;
        });
        
        priority_queue<int, vector<int>, greater<int>> minHeap;
        long long sum = 0;
        long long maxScore = 0;
        
        for (int i = 0; i < n; i++) {
            sum += pairs[i].first;
            minHeap.push(pairs[i].first);
            
            if (minHeap.size() > k) {
                sum -= minHeap.top();
                minHeap.pop();
            }
            
            if (minHeap.size() == k) {
                maxScore = max(maxScore, sum * pairs[i].second);
            }
        }
        
        return maxScore;
    }
};

class Solution:
    def maxScore(self, nums1: List[int], nums2: List[int], k: int) -> int:
        import heapq
        
        pairs = [(nums1[i], nums2[i]) for i in range(len(nums1))]
        pairs.sort(key=lambda x: x[1], reverse=True)
        
        min_heap = []
        sum_nums1 = 0
        max_score = 0
        
        for num1, num2 in pairs:
            sum_nums1 += num1
            heapq.heappush(min_heap, num1)
            
            if len(min_heap) > k:
                sum_nums1 -= heapq.heappop(min_heap)
            
            if len(min_heap) == k:
                max_score = max(max_score, sum_nums1 * num2)
        
        return max_score

public class Solution {
    public long MaxScore(int[] nums1, int[] nums2, int k) {
        int n = nums1.Length;
        var pairs = new (int, int)[n];
        
        for (int i = 0; i < n; i++) {
            pairs[i] = (nums1[i], nums2[i]);
        }
        
        Array.Sort(pairs, (a, b) => b.Item2.CompareTo(a.Item2));
        
        var minHeap = new PriorityQueue<int, int>();
        long sum = 0;
        long maxScore = 0;
        
        foreach (var (num1, num2) in pairs) {
            sum += num1;
            minHeap.Enqueue(num1, num1);
            
            if (minHeap.Count > k) {
                sum -= minHeap.Dequeue();
            }
            
            if (minHeap.Count == k) {
                maxScore = Math.Max(maxScore, sum * num2);
            }
        }
        
        return maxScore;
    }
}

var maxScore = function(nums1, nums2, k) {
    const n = nums1.length;
    const pairs = [];
    
    for (let i = 0; i < n; i++) {
        pairs.push([nums1[i], nums2[i]]);
    }
    
    pairs.sort((a, b) => b[1] - a[1]);
    
    const minHeap = new MinPriorityQueue();
    let sum = 0;
    let maxScore = 0;
    
    for (let i = 0; i < n; i++) {
        const [val1, val2] = pairs[i];
        
        minHeap.enqueue(val1);
        sum += val1;
        
        if (minHeap.size() > k) {
            sum -= minHeap.dequeue().element;
        }
        
        if (minHeap.size() === k) {
            maxScore = Math.max(maxScore, sum * val2);
        }
    }
    
    return maxScore;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n log n)排序需要 O(n log n)，遍历数组并维护堆需要 O(n log k)
空间复杂度O(n)存储配对数组需要 O(n)，最小堆最多存储 k 个元素

相关题目