力扣632.最小区间
你有 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[i].length <= 50
-105 <= nums[i][j] <= 105
nums[i] 按非递减顺序排列
解析，题目中说了每一条列表都是非递减的，那么那就拥有单调性，即每条列表的元素单调递增，观察一下示例，我们很容易会发现本题就是要找寻一个最小区间，使得这个区间包含列表的一个数字，我们来简单画一下图。emmm算了画工不好，就是我们先设置k个指针，分别访问到第一个每个列表的第一个数据上，然后用最大的数字减去最小的数字，这样就能得到一个区间长度，然后让指向这几个元素的最小项进行+1，移到下一位置上，然后继续比较区间的长度，一直到某一个列表的元素被指针指到头位置，最后进行比对和返回值（题目中的我们定义如果 b-a < d-c 或者在 b-a == d-c 时 a < c，则区间 [a,b] 比 [c,d] 小。指的是最后的区间有可能长度一样，但是指针的位置不一样，我们可以通过这个方法来计算出哪个才是真正的最小的区间）
class Solution {
public int[] smallestRange(List<List<Integer>> nums){
//定义一堆指针
int leftRange = 0;
int rightRange = Integer.MAX_VALUE;
int minRange = rightRange - leftRange;
int max = Integer.MIN_VALUE;
int size = nums.size();
int[] ptrs = new int[size];
//索引0，代表第一个列表，ptrs［0］＝位置
PriorityQueue<Integer> queue = new PriorityQueue<>(new Comparator<Integer>(){
public int compare(Integer index1,Integer index2){
return nums.get(index1).get(ptrs[index1]) - nums.get(index2).get(ptrs[index2]);
//把所有指针所指位置最小的指针放到前面去
}
});
for(int i = 0;i < ptrs.length;i++){
queue.offer(i);
max=Math.max(max,nums.get(i).get(0)); }
//取最大值
while(true){
int minIndex = queue.poll();
int curRange = max - nums.get(minIndex).get(ptrs[minIndex]);
if(curRange < minRange){
minRange = curRange;
leftRange = nums.get(minIndex).get(ptrs[minIndex]);
rightRange = max;
}//比较范围，更新边界
ptrs[minIndex]++;
if(ptrs[minIndex] == nums.get(minIndex).size()){
break;
}
queue.offer(minIndex);
//再找最大值循环
max = Math.max(max,nums.get(minIndex).get(ptrs[minIndex]));
}
//走完了之后返回
int[] result = new int[2];
result[0] = leftRange;
result[1] = rightRange;
return result;
}
}
运行截图：
