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.
Example 1:
Input: nums = [[4,10,15,24,26],[0,9,12,20],[5,18,22,30]] Output: [20,24] Explanation: List 1: [4, 10, 15, 24,26], 24 is in range [20,24]. List 2: [0, 9, 12, 20], 20 is in range [20,24]. List 3: [5, 18, 22, 30], 22 is in range [20,24].
Example 2:
Input: nums = [[1,2,3],[1,2,3],[1,2,3]] Output: [1,1]
思路：核心思想就是：每次取每个list里面最小的，进行比较，取一个range出来，然后那个队列的第二大的进去queue排序，每次poll最小的出来，跟当前三者的max进行计算range，因为当前的start ，end就是可以cover三个list的范围，我们要扫描完所有的元素，得到[start, end] range最小的；注意，每次加入下一个node的时候，要判断是不是比max大，如果大，就更新max；
class Solution {
// [[4,10,15,24,26],
// [0,9,12,20],
// [5,18,22,30]]
class Node {
public int rowIndex;
public int listIndex;
public int value;
public Node(int rowIndex, int listIndex, int value) {
this.rowIndex = rowIndex;
this.listIndex = listIndex;
this.value = value;
}
}
public int[] smallestRange(List<List<Integer>> nums) {
PriorityQueue<Node> pq = new PriorityQueue<Node>((a, b) -> (a.value - b.value));
int start = -1; int end = -1;
int max = Integer.MIN_VALUE;
for(int i = 0; i < nums.size(); i++) {
int first = nums.get(i).get(0);
pq.offer(new Node(i, 0, first));
max = Math.max(max, first);
}
int range = Integer.MAX_VALUE;
while(pq.size() == nums.size()) {
Node node = pq.poll();
if(max - node.value < range) {
range = max - node.value;
start = node.value;
end = max;
}
// add next node;
if(node.listIndex + 1 < nums.get(node.rowIndex).size()) {
Node newnode = new Node(node.rowIndex,
node.listIndex + 1,
nums.get(node.rowIndex).get(node.listIndex + 1));
pq.offer(newnode);
if(newnode.value > max) {
max = newnode.value;
}
}
}
return new int[]{start, end};
}
}?
