2099. 找到和最大的长度为 K 的子序列

🟢   🔖  数组 哈希表 排序 堆（优先队列）  🔗 力扣 LeetCode

题目

You are given an integer array nums and an integer k. You want to find a subsequence of nums of length k that has the largest sum.

Return any such subsequence as an integer array of length k.

A subsequence is an array that can be derived from another array by deleting some or no elements without changing the order of the remaining elements.

Example 1:

Input: nums = [2,1,3,3], k = 2

Output: [3,3]

Explanation:

The subsequence has the largest sum of 3 + 3 = 6.

Example 2:

Input: nums = [-1,-2,3,4], k = 3

Output: [-1,3,4]

Explanation:

The subsequence has the largest sum of -1 + 3 + 4 = 6.

Example 3:

Input: nums = [3,4,3,3], k = 2

Output: [3,4]

Explanation:

The subsequence has the largest sum of 3 + 4 = 7.

Another possible subsequence is [4, 3].

Constraints:

• 1 <= nums.length <= 1000
• -10^5 <= nums[i] <= 10^5
• 1 <= k <= nums.length

题目大意

给你一个整数数组 nums 和一个整数 k 。你需要找到 nums 中长度为 k 的 子序列 ，且这个子序列的 和最大。

请你返回 任意 一个长度为 k 的整数子序列。

子序列 定义为从一个数组里删除一些元素后，不改变剩下元素的顺序得到的数组。

示例 1：

输入： nums = [2,1,3,3], k = 2

输出：[3,3]

解释：

子序列有最大和：3 + 3 = 6 。

示例 2：

输入： nums = [-1,-2,3,4], k = 3

输出：[-1,3,4]

解释：

子序列有最大和：-1 + 3 + 4 = 6 。

示例 3：

输入： nums = [3,4,3,3], k = 2

输出：[3,4]

解释：

子序列有最大和：3 + 4 = 7 。

另一个可行的子序列为 [4, 3] 。

提示：

• 1 <= nums.length <= 1000
• -10^5 <= nums[i] <= 10^5
• 1 <= k <= nums.length

解题思路

1. 维护一个大小为 k 的最小堆

   • 为什么用最小堆：
     • 我们需要找到 k 个最大元素，但为了高效处理，我们使用最小堆来维护当前最大的 k 个元素。
     • 堆顶始终是当前最小的元素，可以快速与新的元素比较并替换（如果新元素更大）。
   • 堆中存储的是数组元素及其索引，以便后续排序恢复顺序。

2. 遍历数组 nums

   • 对于每个元素：
     • 如果堆的大小小于 k，直接将元素加入堆。
     • 如果堆的大小等于 k，检查当前元素是否比堆顶元素更大：
       • 如果更大，则移除堆顶元素，将当前元素加入堆。
       • 如果更小，跳过当前元素。
   • 堆中始终保存 k 个最大元素。

3. 从堆中提取元素并按索引排序

   • 堆中元素的顺序不一定与原数组一致，因此需要按照索引对堆中的元素进行排序。
   • 按照索引排序后，提取堆中元素的值构成最终的子序列。

4. 输出结果

   • 返回排序后的子序列，即总和最大的长度为 k 的子序列。

复杂度分析

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

  • 遍历 nums 的时间复杂度：O(n)。
  • 每次 insert 和 pop 的复杂度：O(log k)，最多操作 n 次。
  • 堆排序的复杂度：O(k log k)。
  • 总复杂度：O(n log k + k log k)，对于小的 k，性能非常高效。

• 空间复杂度：O(k)，堆的大小限制为 k。

代码

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number[]}
 */
var maxSubsequence = function (nums, k) {
	const priority = (a, b) => a[0] < b[0]; // 最小堆
	const heap = new MinHeap([], priority);

	// 维护大小为 k 的最小堆
	for (let i = 0; i < nums.length; i++) {
		heap.insert([nums[i], i]);
		if (heap.size() > k) {
			heap.pop(); // 堆大小超过 k 时移除最小值
		}
	}

	// 按索引排序并提取结果
	return heap
		.toArray()
		.sort((a, b) => a[1] - b[1])
		.map((item) => item[0]);
};

class MinHeap {
	constructor(arr = [], priority = (a, b) => a > b) {
		this.heap = arr;
		this.priority = priority;
		for (let i = Math.floor(this.heap.length / 2) - 1; i >= 0; i--) {
			this.heapifyDown(i);
		}
	}

	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 > 0) {
			this.heap[0] = last;
			this.heapifyDown(0);
		}
		return top;
	}

	size() {
		return this.heap.length;
	}

	toArray() {
		return this.heap;
	}

	heapifyDown(i) {
		const n = this.heap.length;
		const left = 2 * i + 1;
		const right = 2 * i + 2;
		let smallest = i;

		if (left < n && this.priority(this.heap[left], this.heap[smallest])) {
			smallest = left;
		}
		if (right < n && this.priority(this.heap[right], this.heap[smallest])) {
			smallest = right;
		}

		if (smallest !== i) {
			[this.heap[i], this.heap[smallest]] = [this.heap[smallest], this.heap[i]];
			this.heapifyDown(smallest);
		}
	}

	heapifyUp(i) {
		while (i > 0) {
			const parent = Math.floor((i - 1) / 2);
			if (this.priority(this.heap[i], this.heap[parent])) {
				[this.heap[i], this.heap[parent]] = [this.heap[parent], this.heap[i]];
				i = parent;
			} else {
				break;
			}
		}
	}
}

相关题目

题号	标题	题解	标签	难度	力扣
215	数组中的第K个最大元素	[✓]	数组 分治 快速选择 2+	🟠	🀄️ 🔗
1005	K 次取反后最大化的数组和	[✓]	贪心 数组 排序	🟢	🀄️ 🔗
1356	根据数字二进制下 1 的数目排序	[✓]	位运算 数组 计数 1+	🟢	🀄️ 🔗
2163	删除元素后和的最小差值		数组 动态规划 堆（优先队列）	🔴	🀄️ 🔗