632. 最小区间

class Solution {
    public int[] smallestRange(List<List<Integer>> nums) {
        int size = nums.size();
        Map<Integer, List<Integer>> indices = new HashMap<Integer, List<Integer>>();
        int xMin = Integer.MAX_VALUE, xMax = Integer.MIN_VALUE;
        for (int i = 0; i < size; i++) {
            for (int x : nums.get(i)) {
                List<Integer> list = indices.getOrDefault(x, new ArrayList<Integer>());
                list.add(i);  // 下标存入进去
                indices.put(x, list);  // 存放元素 - 下标数组[]
                xMin = Math.min(xMin, x);  // 所有元素的最小值、最大值
                xMax = Math.max(xMax, x);
            }
        }

        int[] freq = new int[size];
        int inside = 0;
        int left = xMin, right = xMin - 1;
        int bestLeft = xMin, bestRight = xMax;

        while (right < xMax) {
            right++; // 窗口右移动
            if (indices.containsKey(right)) {
                for (int i : indices.get(right)) {  // i值为小数组下标
                    freq[i]++;
                    if (freq[i] == 1) {  // 小数组数
                        inside++;
                    }
                }
                while (inside == size) {  // k个列表
                    if (right - left < bestRight - bestLeft) {
                        bestLeft = left;
                        bestRight = right;
                    }
                    if (indices.containsKey(left)) {
                        for (int i: indices.get(left)) {
                            freq[i]--;
                            if (freq[i] == 0) {
                                inside--;
                            }
                        }
                    }
                    left++;
                }
            }
        }

        return new int[]{bestLeft, bestRight};
    }
}