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