解把飞花蒙日月
不知天地有清霜
每日一题连续hard，让人有点难受呀。
大部分情况下，hard我都搞不出来呀，思路也是看了大佬的。
思路大概是这样：
- 首先把k个数组合并成一个数组
- 数组的每个元素都是一个结构体
- 结构体包含元素的值以及元素原来所在的数组的索引
- 将合并的数组进行排序
- 在该有序数组中查找一个区间，该区间满足
- 包含了每个原数组的至少一个索引
- 元素的值区间最小
既然是在有序数组中寻找一个区间，就考虑滑动窗口/双指针。
窗口从左到右移动，并记录窗口中存在的原数组索引个数 cnt：
- 如果
cnt小于原数组个数，则左边界右移 - 反之则左移
移动过程中维护一些变量。
class Solution {
private:
static constexpr int RANGE = 1e5;
static bool cmp(pair<int, int> a, pair<int, int> b) {
if (a.first == b.first)
return a.second < b.second;
else return a.first < b.first;
}
public:
vector<int> smallestRange(vector<vector<int>>& nums) {
int n = nums.size();
vector<pair<int, int>> all;
for (int i = 0; i < n; i++) {
for (const int &it : nums[i]) {
all.emplace_back(make_pair(it, i));
}
}
int m = all.size();
sort(all.begin(), all.end(), cmp);
vector<int> hash(n);
hash[all[0].second]++;
int cnt = 1, right = 0, left = 0, ans_left = -RANGE, ans_right = RANGE;
while (left <= right) {
if (cnt < n && right < m - 1) {
right++;
if (hash[all[right].second] == 0)
cnt++;
hash[all[right].second]++;
} else {
if (cnt >= n && (ans_right - ans_left > all[right].first - all[left].first)) {
ans_right = all[right].first;
ans_left = all[left].first;
}
hash[all[left].second]--;
if (hash[all[left].second] == 0)
cnt--;
left++;
}
}
vector<int> ans = {ans_left, ans_right};
return ans;
}
};
