日期: 2024 年 11 月 24 日

目标

你有 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
• -10^5 <= nums[i][j] <= 10^5
• nums[i] 按非递减顺序排列

思路

有 k 个非递减排列的整数列表，找一个最小区间，使得 k 个列表中每个列表至少有一个元素包含其中。所谓最小区间指区间长度最小，如果长度相同，则起点小的区间更小。

可以将元素标记属于哪个列表，然后从小到大排序，使用滑动窗口，找到最小的窗口。

当元素移入/移出窗口，如何判断是否应该从集合中增加/删除列表种类？

• 可以记录每个列表元素的最大下标，如果移出的元素等于该下标则说明窗口内不包含该列表中的元素。元素移入窗口时可以根据最大下标是否小于左边界来判断是否应该增加列表种类，考虑到开始时左边界为 0，应该将数组初始化为 -1。
• 也可以记录每个列表在窗口元素的个数，如果从 0 变为 1 则增加种类，如果从 1 变为 0 则减少。

代码

/**
 * @date 2024-11-24 15:14
 */
public class SmallestRange632 {

    /**
     * 优化代码逻辑
     */
    public int[] smallestRange_v1(List<List<Integer>> nums) {
        List<int[]> list = new ArrayList<>();
        for (int i = 0; i < nums.size(); i++) {
            for (Integer num : nums.get(i)) {
                list.add(new int[]{num, i});
            }
        }
        int[] res = new int[]{0, 1000000};
        list.sort((a, b) -> a[0] - b[0]);
        int n = list.size(), k = nums.size();
        int l = 0;
        int[] typeMaxIndex = new int[k];
        Arrays.fill(typeMaxIndex, -1);
        int types = 0;
        for (int r = 0; r < n; r++) {
            int[] e = list.get(r);
            int right = e[0];
            int type = e[1];
            int lastTypeMaxIndex = typeMaxIndex[type];
            typeMaxIndex[type] = r;
            if (lastTypeMaxIndex < l){
                types++;
            }
            while (types == k) {
                int[] left = list.get(l);
                int lType = left[1];
                if (typeMaxIndex[lType] == l++) {
                    types--;
                    if (right - left[0] < res[1] - res[0]) {
                        res[0] = left[0];
                        res[1] = right;
                    }
                }
            }
        }
        return res;
    }

    public int[] smallestRange(List<List<Integer>> nums) {
        List<int[]> list = new ArrayList<>();
        for (int i = 0; i < nums.size(); i++) {
            for (Integer num : nums.get(i)) {
                list.add(new int[]{num, i});
            }
        }
        int[] res = new int[]{0, 1000000};
        list.sort((a, b) -> a[0] - b[0]);
        int n = list.size(), k = nums.size();
        int l = 0;
        int[] typeMaxIndex = new int[k];
        Set<Integer> set = new HashSet<>();
        for (int r = 0; r < n; r++) {
            int[] e = list.get(r);
            int right = e[0];
            int type = e[1];
            typeMaxIndex[type] = r;
            set.add(type);
            while (set.size() == k) {
                int[] left = list.get(l);
                int lType = left[1];
                if (typeMaxIndex[lType] == l++) {
                    set.remove(lType);
                }
            }
            if (l >= 1 && !set.contains(list.get(l - 1)[1]) && set.size() == k - 1) {
                int left = list.get(l - 1)[0];
                if (right - left < res[1] - res[0]) {
                    res[0] = left;
                    res[1] = right;
                }
            }
        }
        return res;
    }
}

性能