B站
原题
你有 k 个升序排列的整数数组。找到一个最小区间，使得 k 个列表中的每个列表至少有一个数包含在其中。
我们定义如果 b-a < d-c 或者在 b-a == d-c 时 a < c，则区间 [a,b] 比 [c,d] 小。
示例 1:
输入:[[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] 中。
注意:
- 给定的列表可能包含重复元素，所以在这里升序表示 >= 。
- 1 <= k <= 3500
- 10^{-5} <= 元素的值 <= 10^5
思路
重要的是，正如视频中提到的，该如何想到使用多指针的方式来解决这个题目。
将原问题转变成在 k 个列表中定位一个值，并组成集合 S。此时，自然集合中的元素是由 k 个列表中的值组成。那么当前集合 S 中的最大值与最小值的差值即为求解区间的大小。那么，当 S 中的差值最小时的长度，即为问题求解的最小区间的答案。
维护 k 个指针，指向每一个列表中第一个元素的位置。因为数组具有单调性，我们可以按照如下方式进行迭代，进而找到最小区间：
- 维护最小区间：k 个指针指向的元素中的最小值与最大值之差
- 将最小值所在的位置向右移动
- 当某一个指针超出所在列表长度时，跳出循环
代码
vector<vector<int>> _nums;
struct cmp{
bool operator() (const pair<int, int>& a, const pair<int, int>& b) {
return _nums[a.first][a.second] > _nums[b.first][b.second];
}
};
class Solution {
public:
vector<int> smallestRange(vector<vector<int>>& nums) {
// 4 10 15
// 0 9 12
// 5 18 22
// 最小堆 {4, 0, 5} -> {4, 9, 5}
// -> {10, 0, 5}
_nums = nums;
priority_queue<pair<int, int>, vector<pair<int, int>>, cmp> pq;
int ma = -1e5, l = -1e5, r = 1e5;
for (int i = 0; i < nums.size(); ++i) {
pq.push({i, 0});
ma = max(ma, nums[i][0]);
}
while (true) {
auto pa = pq.top();
pq.pop();
if (ma - nums[pa.first][pa.second] < r - l) {
l = nums[pa.first][pa.second], r = ma;
}
if (++pa.second >= nums[pa.first].size()) break;
pq.push(pa);
ma = max(ma, nums[pa.first][pa.second]);
}
return {l, r};
}
};复杂度分析
时间复杂度：O(k * n * logk) n 为列表平均长度，k 为列表个数
空间复杂度：O(k)
参考
[1]. LeetCode 原题. https://leetcode-cn.com/problems/smallest-range-covering-elements-from-k-lists/
欢迎分享，引用。若转载，请联系我，谢谢配合。 本文地址：https://qoogle.top/xiaoxu-tutorial-leetcode-632-smallest-range-covering-elements-from-k-lists/
3refugees