你有 k 个 非递减分列 的整数列表。找到一个 最小 区间，使得 k 个列表中的每个列表至少有一个数包罗在此中。
我们界说如果 b-a < d-c 大概在 b-a == d-c 时 a < c，则区间 [a,b] 比 [c,d] 小。
示例 1：
输入：nums = [[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] 中。
示例 2：
输入：nums = [[1,2,3],[1,2,3],[1,2,3]]
输出：[1,1]
提示：
nums.length == k
1 <= k <= 3500
1 <= nums.length <= 50
-10^5 <= nums[j] <= 10^5
nums 按非递减序次分列
java代码：
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<Integer>(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}; }} |
