跳至主要內容

2542. 最大子序列的分数

2542. 最大子序列的分数

🟠   🔖  贪心 数组 排序 堆（优先队列）  🔗 力扣open in new window LeetCodeopen in new window

题目

You are given two 0-indexed integer arrays nums1 and nums2 of equal length n and a positive integer k. You must choose a subsequence of indices from nums1 of length k.

For chosen indices i0, i1, ..., ik - 1, your score is defined as:

  • The sum of the selected elements from nums1 multiplied with the minimum of the selected elements from nums2.
  • It can defined simply as: (nums1[i0] + nums1[i1] +...+ nums1[ik - 1]) * min(nums2[i0] , nums2[i1], ... ,nums2[ik - 1]).

Return the maximum possible score.

A subsequence of indices of an array is a set that can be derived from the set {0, 1, ..., n-1} by deleting some or no elements.

Example 1:

Input: nums1 = [1,3,3,2], nums2 = [2,1,3,4], k = 3

Output: 12

Explanation:

The four possible subsequence scores are:

  • We choose the indices 0, 1, and 2 with score = (1+3+3) * min(2,1,3) = 7.
  • We choose the indices 0, 1, and 3 with score = (1+3+2) * min(2,1,4) = 6.
  • We choose the indices 0, 2, and 3 with score = (1+3+2) * min(2,3,4) = 12.
  • We choose the indices 1, 2, and 3 with score = (3+3+2) * min(1,3,4) = 8.

Therefore, we return the max score, which is 12.

Example 2:

Input: nums1 = [4,2,3,1,1], nums2 = [7,5,10,9,6], k = 1

Output: 30

Explanation:

Choosing index 2 is optimal: nums1[2] * nums2[2] = 3 * 10 = 30 is the maximum possible score.

Constraints:

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

题目大意

给你两个下标从 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

解题思路

  1. 按权重排序：将 nums2 的值作为排序依据，从大到小排序，这样确保我们优先处理较大的最小权重值。

  2. 维护最大子序列和：

    • 使用一个大小为 k 的最小堆存储当前选定的 nums1 中的数字。
    • 保持堆中有 k 个数时，其总和即为当前的最大子序列和。

  3. 计算分数：

    • 遍历 nums2 的权重数组，对于每个权重，尝试将对应的 nums1 中的数字加入堆：
      • 如果堆大小小于 k，直接加入。
      • 如果堆大小等于 k，用当前值替换堆顶（最小值）以尝试增加总和，并更新最大得分。

复杂度分析

  • 时间复杂度：O(n log n + n log k)

    • 排序：对 nums2 降序排序，时间复杂度为 O(n log n)。
    • 堆操作：遍历每个元素时，堆中插入或移除的操作为 O(log k)，总共有 n 个元素，因此时间复杂度为 O(n log k)。
    • 总时间复杂度：O(n log n + n log k)。

  • 空间复杂度：O(n + k)

    • 存储堆的空间复杂度为 O(k)。
    • 存储排序后的数组需要 O(n)。
    • 总空间复杂度为 O(n + k)。

代码

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @param {number} k
 * @return {number}
 */
var maxScore = function (nums1, nums2, k) {
	// 将 nums2 的权重和对应的 nums1 组合，并按权重降序排序
	const pairs = nums1.map((num, idx) => [num, nums2[idx]]);
	pairs.sort((a, b) => b[1] - a[1]);

	let curSum = 0; // 当前堆中数字的和
	let maxScore = 0; // 最大得分
	let minHeap = new MinHeap(); // 最小堆

	// 遍历每个权重
	for (let i = 0; i < pairs.length; i++) {
		const [num1, num2] = pairs[i];

		// 将当前 num1 加入堆
		minHeap.insert(num1);
		curSum += num1;

		// 如果堆中元素已经达到 k 个，计算得分
		if (minHeap.size() == k) {
			maxScore = Math.max(maxScore, curSum * num2);
			curSum -= minHeap.pop();
		}
	}

	return maxScore;
};

class MinHeap {
	constructor() {
		this.heap = [];
	}
	insert(num) {
		this.heap.push(num);
		this.heapifyUp(this.heap.length - 1);
	}
	pop() {
		if (this.heap.length == 0) return null;
		const top = this.heap[0];
		const last = this.heap.pop();
		if (this.heap.length) {
			this.heap[0] = last;
			this.heapifyDown(0);
		}
		return top;
	}
	size() {
		return this.heap.length;
	}
	heapifyUp(i) {
		while (i) {
			const parent = ((i - 1) / 2) | 0;
			if (this.heap[parent] > this.heap[i]) {
				[this.heap[i], this.heap[parent]] = [this.heap[parent], this.heap[i]];
				i = parent;
			} else {
				break;
			}
		}
	}
	heapifyDown(i) {
		let left = i * 2 + 1,
			right = i * 2 + 2,
			min = i;
		if (left < this.heap.length && this.heap[left] < this.heap[min]) {
			min = left;
		}
		if (right < this.heap.length && this.heap[right] < this.heap[min]) {
			min = right;
		}
		if (min !== i) {
			[this.heap[i], this.heap[min]] = [this.heap[min], this.heap[i]];
			this.heapifyDown(min);
		}
	}
}

相关题目

题号标题题解标签难度力扣
502IPO[✓]贪心 数组 排序 1+🔴🀄️open in new window 🔗open in new window
857雇佣 K 名工人的最低成本贪心 数组 排序 1+🔴🀄️open in new window 🔗open in new window
Copyright © 2024 2xiao