你有 k 个升序排列的整数数组。找到一个最小区间，使得 k 个列表中的每个列表至少有一个数包含在其中。
我们定义如果 b-a < d-c 或者在 b-a == d-c 时 a < c，则区间 [a,b] 比 [c,d] 小。
示例 1:
1
2
3
4
5
6
| 输入:[[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
方法一：堆
给定 k 个列表，需要找到最小区间，使得每个列表都至少有一个数在该区间中。该问题可以转化为：从 k 个列表中各取一个数，使得这 k 个数中的最大值与最小值的差最小。
假设这 k 个数中的最小值是第 i 个列表中的 x，对于 任意 j≠i，设第 j 个列表中被选为 k 个数之一的数是 y，为了找到最小区间，y 应该取第 j 个列表中大于等于 x 的最小的数。
使用最小堆维护 k 个指针指向的元素中的最小值，同时维护堆中元素的最大值。初始时，k个指针都指向下标 0 ，最大元素即为所有列表中下标为 0 位置的元素中的最大值。每次从堆中取出最小值（尝试将最小值扩大来获得更小的区间），根据最大值和最小值计算区间，如果当前区间小于最小区间，则更新最小区间，然后将对应列表的指针右移，将新元素加入堆中，并更新堆中元素的最大值。
如果一个列表遍历到末尾，则堆中不会再有该列表的元素，退出循环。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
| class Solution {
public int[] smallestRange(List<List<Integer>> nums) {
int rangeLeft = 0, rangeRight = Integer.MAX_VALUE;
int minRange = rangeRight - rangeLeft;
int max = Integer.MIN_VALUE;
int size = nums.size();
int[] next = new int[size];
PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(new Comparator<Integer>(){
public int compare(Integer index1, Integer index2){
return nums.get(index1).get(next[index1]) - nums.get(index2).get(next[index2]);
}
});
for(int i = 0; i < size; i++){
priorityQueue.offer(i);
max = Math.max(max, nums.get(i).get(0));
}
while(true){
int minIndex = priorityQueue.poll();
int curRange = max - nums.get(minIndex).get(next[minIndex]);
if(curRange < minRange){
minRange = curRange;
rangeLeft = nums.get(minIndex).get(next[minIndex]);
rangeRight = max;
}
next[minIndex]++;
if(next[minIndex] == nums.get(minIndex).size()){
break;
}
priorityQueue.offer(minIndex);
max = Math.max(max, nums.get(minIndex).get(next[minIndex]));
}
return new int[]{rangeLeft, rangeRight};
}
}
|
时间复杂度O(n k log k)，n 是所有列表的平均长度，k是列表数量。所有指针移动次数为 nk，操作堆的时间复杂度为O(logk)。
空间复杂度O(k)，堆中维护 k 个元素。