632. 最小区间
你有 k 个升序排列的整数数组。找到一个最小区间，使得 k 个列表中的每个列表至少有一个数包含在其中。
我们定义如果 b-a < d-c 或者在 b-a == d-c 时 a < c，则区间 [a,b] 比 [c,d] 小。
示例 1:
输入:[[4,10,15,24,26], [0,9,12,20], [5,18,22,30]]
输出: [20,24]
解释:
列表 1：[4, 10, 15, 24, 26]，24 在区间 [20,24] 中。
列表 2：[0, 9, 12, 20]，20 在区间 [20,24] 中。
列表 3：[5, 18, 22, 30]，22 在区间 [20,24] 中。
注意:
给定的列表可能包含重复元素，所以在这里升序表示 >= 。
1 <= k <= 3500
-105 <= 元素的值 <= 105
对于使用Java的用户，请注意传入类型已修改为List<List>。重置代码模板后可以看到这项改动。
class Solution {
public int[] smallestRange(List<List<Integer>> nums) {
if(nums == null || nums.size() == 0)
return null;
int len = nums.size();
PriorityQueue<Pair> queue = new PriorityQueue<>(Comparator.comparingInt(p -> p.num));
int[] res = new int[2];
res[1] = Integer.MAX_VALUE;
//maxNum 记录每一次遍历中k个数组的最大值
int maxNum = Integer.MIN_VALUE;
//初始化优先队列，将k个数组的第一个数字入队
for(int i = 0;i<len;i++){
int num = nums.get(i).get(0);
maxNum = Math.max(maxNum,num);
queue.add(new Pair(i,0,num));
}
//这里的循环退出条件是队列为空，也可以写成双层循环遍历数组
while(!queue.isEmpty()){
//每次遍历，先从队列中取出当前最小值
Pair pair = queue.poll();
int num = pair.num;
//如果（当前最小值，当前最大值）的区间范围更小，则修改res数组
if(res[1] - res[0] > maxNum - num){
res[0] = num;
res[1] = maxNum;
}
int row = pair.row;
//右移
int col = pair.col + 1;
//如果右移后超出数组长度，此时退出循环，即已经找到最小的区间了
if(nums.get(row).size() == col){
break;
}
//下一个数，是当前数右边的数
int nextNum = nums.get(row).get(col);
//下一个数继续入队列
queue.add(new Pair(row,col,nextNum));
//更新当前最大值
maxNum = Math.max(maxNum,nextNum);
}
return res;
}
//定义一个类，用来记录遍历过程中，每个数字所在的行、列和数字对应的值
class Pair{
public Integer row;
public Integer col;
public Integer num;
public Pair(Integer row,Integer col,Integer num){
this.row = row;
this.col = col;
this.num = num;
}
}
}
官方的解法
class Solution {
public int[] smallestRange(List<List<Integer>> nums) {
int minx = 0, miny = Integer.MAX_VALUE, max = Integer.MIN_VALUE;
int[] next = new int[nums.size()];
boolean flag = true;
// 最小堆维护的是当前的最小值，在哪个列表中。注意该堆的比较器。
PriorityQueue<Integer> min_queue = new PriorityQueue<Integer>((i,j) -> nums.get(i).get(next[i])-nums.get(j).get(next[j]));
// 初始化堆
for(int i=0;i<nums.size();i++){
min_queue.offer(i);
max = Math.max(max,nums.get(i).get(0));
}
// 从堆中取得当前最小元素所在的列表。根据next[i]，取得其所在位置，多路指针法，类似于丑数；
// 经前面分期，第二个列表就是min_i在其列表的后一位及其之前其他数字组成的区间。最小值由最小堆（决定min_i）及next[min_i]维护，
// 最大值由max = Math.max(max, nums.get(min_i).get(next[min_i]))维护。
for(int i=0;i<nums.size()&&flag;i++){
for(int j=0;j<nums.get(i).size()&&flag;j++){
int min_i = min_queue.poll();
// 选择更小的区间
if(miny-minx> max - nums.get(min_i).get(next[min_i])){
miny = max;
minx = nums.get(min_i).get(next[min_i]);
}
// 由于next改变，min_i加入堆后，堆结构也会改变
next[min_i]++;
if(next[min_i]>=nums.get(min_i).size()){
flag = false;
break;
}
min_queue.offer(min_i);
max = Math.max(max, nums.get(min_i).get(next[min_i]));
}
}
return new int[]{minx,miny};
}
}