K个数组,每个数组元素都已排好序,让找出能囊括每个数组至少一个元素的最小范围。初始时K个指针都指向0元素,为了让范围尽可能小,下一个候选应当是当前K中最小的前移,移动其余元素都只会让范围不变或更大,是无谓的尝试。同理依此类推。为了每次快速定位最小元素,用min heap。
/*
* @lc app=leetcode id=632 lang=cpp
*
* [632] Smallest Range Covering Elements from K Lists
*/
// @lc code=start
class Solution {
public:
vector<int> smallestRange(vector<vector<int>>& nums) {
const int N = nums.size();
vector<int> pts(N, 0);
const auto cmp = [](pair<int, int> &a, pair<int, int> &b) {
return a.first > b.first;
};
vector<int> range = {INT_MAX, INT_MIN};
priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(cmp)> pq(cmp);
for (int i = 0; i < N; ++i) {
const auto num = nums[i][0];
pq.push({num, i});
range[0] = min(range[0], num);
range[1] = max(range[1], num);
}
auto res = range;
while (true) {
auto t = pq.top(); pq.pop();
int i = t.second;
++pts[i];
if (pts[i] < nums[i].size()) {
int v = nums[i][pts[i]];
pq.push({v, i});
range[0] = pq.top().first;
range[1] = max(range[1], v);
} else break;
if (range[1] - range[0] < res[1] - res[0]) {
res = range;
}
}
return res;
}
};
// @lc code=end