算法

(双指针区间维护)

• 首先由于各个序列升序排列，开始利用current数组，筛选出所有序列的最小值中最大的数字，因为最终答案的右边界肯定大于等于该值，所以从该值开始。
• 然后在for循环内对所有序列遍历，使得每个currenti保存了每个序列中最接近maxValue并且小于maxValue的数字下标，同时选出每个序列中最接近maxValue并且小于maxValue的数字最小值。
• 得到左右边界后，判断是否更新答案。
• 如果当前currenti指向的不是该序列的最后一个数字，则currenti++，即右移，将对应数字设为右边界，因为要将之前的最小值从维护的区间弹出，重新维护。
• 如果指向为最后一个则无法移动，返回结果即可。

C++ 代码

class Solution {
public:
    vector<int> smallestRange(vector<vector<int>>& nums) {
        int current[nums.size()];
        memset(current, 0 ,sizeof(current));
        vector<int> range;
        range.push_back(0);
        range.push_back(0);
        int result = 0x3f3f3ff, maxValue = -0x3f3f3f3f, maxIndex = 0;
        bool flag= 1;
        for(int i = 0; i < nums.size(); i++){       //筛选出所有序列的最小值中最大的数字
            if(nums[i][current[i]] > maxValue){
              maxIndex = i;                
              maxValue = nums[i][current[i]]; 
            }
        }
        while(flag) {
            int minIndex = 0, minValue = 0x3f3f3ff;
            for(int i = 0;i < nums.size();i++){
                while(current[i] + 1 < nums[i].size() && nums[i][current[i] + 1] <= maxValue){  //找到第i个序列中最接近maxValue的数字的下标
                    current[i]++;
                }
                if(nums[i][current[i]] < minValue){      //找出所有序列中最接近且小于等于maxValue的值里面的最小值
                    minIndex = i;         
                    minValue = nums[i][current[i]]; 
                }
            }
            if(maxValue - minValue < result){    //更新答案
                result = maxValue - minValue;
                range[0] = minValue;
                range[1] = maxValue;
            }
            if(current[minIndex] == nums[minIndex].size() - 1) {  //如果minIndex到达尾部，则无法移动
                flag = 0;
            }
            else {
                current[minIndex]++;    //current[minIndex]继续向右移动
                maxIndex = minIndex;    
                maxValue = nums[maxIndex][current[maxIndex]];  //将上一轮最小值右侧的数字设为下一轮的最大值，将之前区间内的最小值去除，重新维护区间。
            }
        }
        return range; 
    }
};

Java 代码

class Solution {
    public int[] smallestRange(List<List<Integer>> nums) {
        // [start, end]
        // set : one element from each list  size = k
        // max - min
        // treeset
        TreeSet<Elem> candidate = new TreeSet<>((o1, o2) 
        -> Integer.compare(o1.val, o2.val) == 0 ? Integer.compare(o1.list, o2.list)
        : Integer.compare(o1.val, o2.val));

        int n = nums.size();
        for (int i = 0; i < n; ++i) {
            Elem e = new Elem(i, 0, nums.get(i).get(0));
            candidate.add(e);
        }

        int range = Integer.MAX_VALUE;
        int[] res = new int[2];
        while (candidate.size() == n) {
            int max = candidate.last().val;
            int min = candidate.first().val;
            if (max - min < range) {
                range = max - min;
                res[0] = min;
                res[1] = max;
            }
            Elem f = candidate.pollFirst();
            if (f.idx + 1 < nums.get(f.list).size()) {
                Elem next = new Elem(f.list, f.idx + 1, nums.get(f.list).get(f.idx + 1));
                candidate.add(next);
            }
        }

        return res;
    }

    class Elem {
        int list;
        int idx;
        int val;
        public Elem(int list, int idx, int val) {
            this.list = list;
            this.idx = idx;
            this.val = val;
        }
    }
}