?LeetCode刷題實戰(zhàn)632：最小區(qū)間
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 - c or a < c if b - a == d - c.
你有 k 個 非遞減排列 的整數(shù)列表。找到一個 最小 區(qū)間，使得 k 個列表中的每個列表至少有一個數(shù)包含在其中。
我們定義如果 b-a < d-c 或者在 b-a == d-c 時 a < c，則區(qū)間 [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 在區(qū)間 [20,24] 中。
列表 2：[0, 9, 12, 20]，20 在區(qū)間 [20,24] 中。
列表 3：[5, 18, 22, 30]，22 在區(qū)間 [20,24] 中。
示例 2：
輸入：nums = [[1,2,3],[1,2,3],[1,2,3]]
輸出：[1,1]
主要思路：
首先，最小區(qū)間要：
1.最短
2.在長度相等時，起點最小
為了滿足2，取所有列表的最小值放入?yún)^(qū)間中，又要使區(qū)間變短，那這個區(qū)間的最小值應該往右移，也就是把列表中，這個值的下一位拿出來替代它，在更新的過程中，記錄區(qū)間的長度，就能找到最小區(qū)間。
用一個最小堆存放元素(num,a,b)，a為num所在的列表下標，b為num在列表中的下標,最小值為堆頂元素，用一個變量記錄最大值
class Solution {
private:
struct node
{
int val, indexa, indexb;
//記錄當前元素的值和它在哪個區(qū)間，區(qū)間的哪個位置
node(int v, int a, int b):val(v), indexa(a), indexb(b){}
};
friend bool operator > (const struct node& a, const struct node& b)
{
return (a.val > b.val);
};
public:
vector<int> smallestRange(vector<vector<int>>& nums) {
//區(qū)間的最大值
int mx = nums[0][0];
//最小區(qū)間的長度
int dis = 200000;
int mxindexa = 0, mxindexb = 0;
//最小區(qū)間的左右端點
int left, right;
//auto cmp = [](node left, node right){return left.val > right.val;};
//建立最小堆
priority_queue<node, vector<node>, greater<node> > pq;
//每個元素的最小值入堆,構成初始區(qū)間
for(int i = 0; i < nums.size(); i++)
{
pq.push(node(nums[i][0], i, 0));
//記錄最大值和它所在的區(qū)間
if(mx < nums[i][0])
{
mx = nums[i][0];
mxindexa = i;
}
}
node cur = pq.top();
//替代區(qū)間最小值的下一個元素
int next;
while(1)
{
//更換掉當前區(qū)間的最小值
cur = pq.top();
pq.pop();
//更新最小區(qū)間
if(mx - cur.val < dis)
{
dis = mx - cur.val;
left = cur.val;
right = mx;
}
//如果當前元素已經(jīng)是所在列表的末尾
if(cur.indexb + 1 >= nums[cur.indexa].size()) break;
//用列表中元素的下一個元素替代它
next = nums[cur.indexa][cur.indexb + 1];
pq.push(node(next, cur.indexa, cur.indexb + 1));
if(mx < next) mx = next;
}
return {left, right};
}
};