我们有k升序排列的整数数组,先思考如何找到一个包含列表中至少一个数的区间?
我们用k个指针指向k个列表的开始元素,求出这k个数的最大最小值,那么区间[min, max]
就至少包含了每个列表的一个元素,但这个区间可能不是最小的区间,我们考虑如何缩小这个区间。
因为列表都是升序的,要想缩小这个区间,我们只能将最小的元素移出区间,同时为了确保区间包含该元素所在的列表的一个元素,我们把这个最小元素后面的元素加到区间里。如果我们移出的元素不是当前区间最小的,而是其他元素,那么区间[min, max]
中min
不会改变,而max
可能会变大,所以区间只会增大或不变而不会减小。
我们使用k个指针分别指向列表的开始元素,每次遍历这k个元素,找到其中最大最小值,如果当前区间较小,就更新答案,然后将指向最小值元素的指针加上1,表示将后面的元素加入到区间中。
因为我们是从小到大枚举的指针,所以找到的最小长度的区间一定是最靠左的,也即满足题目条件b-a == d-c 时 a < c
的。
class Solution {
public int[] smallestRange(List<List<Integer>> nums) {
// k个指针,p[i]指向列表i的第p[i]个元素
int[] p = new int[nums.size()];
int[] ans = new int[]{0, (int)1e8};
while(true){
int min = Integer.MAX_VALUE;
int max = Integer.MIN_VALUE;
int minp = 0;
// 遍历当前指针所指元素,找到最大最小值,同时记录最小值所在列表
for(int i = 0; i < p.length; i++){
int num = nums.get(i).get(p[i]);
if(num < min){
min = num;
minp = i;
}
if(num > max){
max = num;
}
}
// 更新答案
if(max - min < ans[1] - ans[0]){
ans[1] = max;
ans[0] = min;
}
// 更新指向最小值的指针,如果指针超出了列表大小,就结束循环
p[minp]++;
if(p[minp] >= nums.get(minp).size()){
break;
}
}
return ans;
}
}
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
我们不用每次都遍历k个指针,可以将这k个指针所指元素放入到小顶堆中,每次从堆中弹出这个元素,得到最小值,同时用一个变量维护保存最大值即可。
class Solution {
public int[] smallestRange(List<List<Integer>> nums) {
int[] ans = new int[]{0, (int)1e8};
// 小顶堆,堆中元素是3个长度的数组,
// c[0]表示元素的值,c[1]表示元素所在的列表,c[2]表示列表中的索引
Queue<int[]> heap = new PriorityQueue<>((a, b) -> a[0] - b[0]);
int max = Integer.MIN_VALUE;
// 初始化堆
for(int i = 0; i < nums.size(); i++){
int[] c = new int[]{nums.get(i).get(0), i, 0};
heap.add(c);
max = Math.max(max, c[0]);
}
while(true){
// 将当前堆中最小元素弹出
int[] c = heap.remove();
if(max - c[0] < ans[1] - ans[0]){
ans[0] = c[0];
ans[1] = max;
}
// 指向最小元素所在列表的下一个元素,如果没有,则结束循环
c[2]++;
if(c[2] >= nums.get(c[1]).size()){
break;
}
// 加入堆,同时更新最大值
c[0] = nums.get(c[1]).get(c[2]);
heap.add(c);
max = Math.max(max, c[0]);
}
return ans;
}
}