632. Smallest Range
632. Smallest Range
题目: https://leetcode.com/problems/smallest-range/
难度: Hard
题意：
- 给定n个序列，求一个最小区间，使得每个序列至少一个数在这个区间里面
思路：
- 采用移动区间的做法。如果区间左端点为l，那么我们需要在所有的序列中寻找比l大的最小数，构成一个区间[l, r]
- 首先，将所有序列的第一个数字入堆，我们记录一个最大值。这时候堆里面的数形成一个区间，判断和记录下来。接着区间开始移动，将堆里面的最小数弹出丢掉，再从这个最小数所在的序列取出下一个数放进堆，又形成一个区间，判断和记录下来。如此循环，直到其中一个序列没有数可以进堆
解法：
class Solution {
public:
struct myData {
int x, y, value;
myData(int _x = 0, int _y = 0, int _value = 0): x(_x), y(_y), value(_value) {}
bool operator<(const myData &b) const {
return value > b.value;
}
};
vector<int> smallestRange(vector<vector<int>>& nums) {
int l = -10000000, r = -10000000;
priority_queue<myData> q;
int res = -10000000;
for (int i = 0;i < nums.size();i++) {
q.push(myData(i, 0, nums[i][0]));
res = res > nums[i][0] ? res : nums[i][0];
}
while (q.size() == nums.size()) {
myData t = q.top();
q.pop();
if (l == -10000000 || (res - t.value) < (r - l)) {
l = t.value;
r = res;
}
if (t.y + 1 < nums[t.x].size()) {
q.push(myData(t.x, t.y + 1, nums[t.x][t.y + 1]));
res = res > nums[t.x][t.y + 1] ? res : nums[t.x][t.y + 1];
}
}
vector<int> ret;
ret.push_back(l);
ret.push_back(r);
return ret;
}
};
