632. 最小区间

🔴   🔖  贪心 数组 哈希表 排序 滑动窗口 堆（优先队列）  🔗 力扣 LeetCode

题目

You have k lists of sorted integers in non-decreasing order. Find the smallest range that includes at least one number from each of the k lists.

We define the range [a, b] is smaller than range [c, d] if b - a < d - cor a < c if b - a == d - c.

Example 1:

Input: nums = [[4,10,15,24,26],[0,9,12,20],[5,18,22,30]]

Output: [20,24]

Explanation:

List 1: [4, 10, 15, 24,26], 24 is in range [20,24].

List 2: [0, 9, 12, 20], 20 is in range [20,24].

List 3: [5, 18, 22, 30], 22 is in range [20,24].

Example 2:

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

Output: [1,1]

Constraints:

• nums.length == k
• 1 <= k <= 3500
• 1 <= nums[i].length <= 50
• -10^5 <= nums[i][j] <= 10^5
• nums[i] is sorted in non-decreasing order.

题目大意

你有 k 个 非递减排列 的整数列表。找到一个 最小 区间，使得 k 个列表中的每个列表至少有一个数包含在其中。

我们定义如果 b-a < d-c 或者在 b-a == d-c 时 a < c，则区间 [a,b] 比 [c,d] 小。

示例 1：

输入： nums = [[4,10,15,24,26], [0,9,12,20], [5,18,22,30]]

输出：[20,24]

解释：

列表 1：[4, 10, 15, 24, 26]，24 在区间 [20,24] 中。

列表 2：[0, 9, 12, 20]，20 在区间 [20,24] 中。

列表 3：[5, 18, 22, 30]，22 在区间 [20,24] 中。

示例 2：

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

输出：[1,1]

提示：

• nums.length == k
• 1 <= k <= 3500
• 1 <= nums[i].length <= 50
• -10^5 <= nums[i][j] <= 10^5
• nums[i] 按非递减顺序排列

解题思路

可以使用最小优先队列来维护每个数组当前元素的最小值。通过这个队列，可以快速获取当前区间的最小值和最大值。

• 首先，将每个数组的第一个元素（即最小的元素）放入优先队列中，并记录当前的最大元素。
• 然后，不断从队列中取出最小元素，同时将这个元素所在数组的下一个元素加入队列中，并更新当前的最大值。
• 在每一步中，计算当前区间的大小，并与当前最优区间进行比较，如果区间更小，则更新最优解。

当其中一个数组被遍历完时（即它的所有元素都被处理完），就无法继续扩展区间了，此时循环结束。

复杂度分析

• 时间复杂度：O(n log k)，其中 n 是所有数组的元素总数，k 是数组的个数。每次操作都涉及到从堆中取出最小元素并插入新元素，堆的大小最多为 k，所以每次操作的时间复杂度是 O(log k)，每个数组的所有元素都会被处理一次，共处理 n 次。
• 空间复杂度：O(k)，优先队列的大小最多为 k。

代码

/**
 * @param {number[][]} nums
 * @return {number[]}
 */
var smallestRange = function (nums) {
	let rangeStart = 0,
		rangeEnd = Infinity;
	let maxVal = -Infinity;

	// 初始化最小堆为每个数组的第一个元素
	let minHeap = new MinHeap({ priority: (i) => i[0] });
	for (let i = 0; i < nums.length; i++) {
		minHeap.enqueue([nums[i][0], i, 0]);
		maxVal = Math.max(maxVal, nums[i][0]);
	}

	// 当其中一个数组被遍历完时，结束循环
	while (minHeap.size() == nums.length) {
		// 出堆
		const [minVal, numsIdx, itemIdx] = minHeap.dequeue();
		// 更新最优解
		if (maxVal - minVal < rangeEnd - rangeStart) {
			rangeStart = minVal;
			rangeEnd = maxVal;
		}
		// 如果有下一个数，入堆
		if (itemIdx + 1 < nums[numsIdx].length) {
			const nextVal = nums[numsIdx][itemIdx + 1];
			minHeap.enqueue([nextVal, numsIdx, itemIdx + 1]);
			maxVal = Math.max(maxVal, nextVal);
		}
	}
	return [rangeStart, rangeEnd];
};

// 最小优先队列
class MinHeap {
	constructor({ priority }) {
		this.heap = [];
		this.priority = priority;
	}

	enqueue(val) {
		this.heap.push(val);
		this.heapifyUp(this.heap.length - 1);
	}
	dequeue() {
		if (this.size() == 0) return null;
		if (this.size() == 1) return this.heap.pop();

		const min = this.heap[0];
		this.heap[0] = this.heap.pop();
		this.heapifyDown(0);
		return min;
	}
	heapifyUp(i) {
		while (i > 0) {
			const parent = ((i - 1) / 2) | 0;
			if (
				this.getPriority(this.heap[i]) < this.getPriority(this.heap[parent])
			) {
				[this.heap[i], this.heap[parent]] = [this.heap[parent], this.heap[i]];
				i = parent;
			} else {
				break;
			}
		}
	}
	heapifyDown(i) {
		const left = i * 2 + 1,
			right = i * 2 + 2;
		let min = i;
		if (
			left < this.size() &&
			this.getPriority(this.heap[min]) > this.getPriority(this.heap[left])
		) {
			min = left;
		}
		if (
			right < this.size() &&
			this.getPriority(this.heap[min]) > this.getPriority(this.heap[right])
		) {
			min = right;
		}
		if (min !== i) {
			[this.heap[i], this.heap[min]] = [this.heap[min], this.heap[i]];
			this.heapifyDown(min);
		}
	}
	getPriority(item) {
		return this.priority(item);
	}
	size() {
		return this.heap.length;
	}
}

相关题目

题号	标题	题解	标签	难度
76	最小覆盖子串	[✓]	哈希表 字符串 滑动窗口