每日一题 好题反思 hard 最小区间
题目

题目描述

你有 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] 按非递减顺序排列

样例

blablabla

我的做法（初见）
k很大3500 大概一共17w的元素 但是区间内是单调的 考虑二分查找
从答案入手 让区间小 那就是左端点尽量往右，右端点尽量往左。
那么最优左端点一定满足 小于等于 k个数组中最大值的最小值 (因为大于的话 会有一个数组覆盖不到)
然后根据每一个左端点 进行查找。

但是要求相同区间大小下找到左端点尽量小的那个。
所以枚举每一个小于那个找到的最优左端点，二分查找能覆盖的右端点，并取最大值计算长度。如果长度确实小了，就更新左右端点
但是时间复杂度爆了 n * k * logn

题解更优做法
优先队列/滑动窗口

优先队列是优化 相同区间大小下找到左端点尽量小的那个 每次枚举左端点都是最小的。
右端点是每一个列表的最大值。保证一定能实现区间覆盖。
//通过入堆三元组进行优化

算法1

(优先队列举) $O(Llogk )$

循环 O(L) 次，每次循环需要 O(logk) 的时间操作堆。

时间复杂度

参考文献

java 代码

  public int[] smallestRange(List<List<Integer>> nums) {
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
        int r = Integer.MIN_VALUE;
        for (int i = 0; i < nums.size(); i++) {
            // 把每个列表的第一个元素入堆
            int x = nums.get(i).get(0);
            pq.offer(new int[]{x, i, 0});
            r = Math.max(r, x);
        }

        int ansL = pq.peek()[0]; // 第一个合法区间的左端点
        int ansR = r; // 第一个合法区间的右端点
         //这个while的判断条件如上所描述，拿我们的 下标 + 1 和 当前列表的size做比较，如果条件成立，则继续维护我们的最小堆
        while (pq.peek()[2] + 1 < nums.get(pq.peek()[1]).size()) { //  这一句需要挺深的java功底    堆顶列表有下一个元素
            int[] top = pq.poll();
            top[0] = nums.get(top[1]).get(++top[2]); // 堆顶列表的下一个元素
            r = Math.max(r, top[0]); // 更新合法区间的右端点
            pq.offer(top); // 入堆（复用 int[]，提高效率）
            int l = pq.peek()[0]; // 当前合法区间的左端点
            if (r - l < ansR - ansL) {
                ansL = l;
                ansR = r;
            }
        }

        /*
          while(pq.peek()[2] + 1 < nums.get(pq.peek()[1]).size()){
            int[] p = pq.poll();
            //拿到我们当前列表的下一个元素
            int nxtX = nums.get(p[1]).get(p[2] + 1);
            //更新value
            p[0] = nxtX;
            //更新下标
            p[2] += 1;
            //在更新答案前，我们先维护新的右端点
            r = Math.max(r, nxtX);
            //在更新左端点之前，先把新的 {x, i, 0 + 1}放到堆内
            pq.offer(p);
            //更新下标
            int l = pq.peek()[0];
            //如果当前的区间更小，则更新答案
            if(r - l < ansR - ansL){
                //System.out.println(l + ", " + r);
                ansL = l;
                ansR = r;
            }
        }
        */
        return new int[]{ansL, ansR};
    }

cpp代码
class Solution {
public:
    vector<int> smallestRange(vector<vector<int>>& nums) {
        typedef vector<int> VI;
        VI result;
        priority_queue<VI, vector<VI>, greater<VI>> record;
        int maxv = INT_MIN;

        for(int i = 0; i < nums.size(); i ++) {
            record.push({nums[i][0], i, 0});
            maxv = max(maxv, nums[i][0]);
        }

        while(record.size()) {
            auto temp = record.top();
            record.pop();
            int left = temp[0], right = maxv;
            if(result.empty() || result[1] - result[0] > right - left) {
                result = {left, right};
            }
            int i = temp[1], j = temp[2] + 1;
            if(j < nums[i].size()) {
                record.push({nums[i][j], i, j});
                maxv = max(maxv, nums[i][j]);
            } else {
                break;
            }
        }
        return result;
    }
};

算法2

(排序+滑窗) $O(n^2)$

把所有元素都合在一起排序，可以得到如下结果：合法区间等价于 pairs 的一个连续子数组，满足列表编号 0,1,2,…,k−1 都在这个子数组中。由于子数组越长，越能包含 0,1,2,…,k−1 所有编号，有单调性，可以用滑动窗口解决。

时间复杂度

参考文献

java 代码

class Solution {
    public int[] smallestRange(List<List<Integer>> nums) {
        int sumLen = 0;
        for (List<Integer> list : nums) {
            sumLen += list.size();
        }

        int[][] pairs = new int[sumLen][2];
        int pi = 0;
        for (int i = 0; i < nums.size(); i++) {
            for (int x : nums.get(i)) {
                pairs[pi][0] = x;
                pairs[pi++][1] = i;
            }
        }
        Arrays.sort(pairs, (a, b) -> a[0] - b[0]);

        int ansL = pairs[0][0];
        int ansR = pairs[sumLen - 1][0];
        int empty = nums.size();
        int[] cnt = new int[empty];
        int left = 0;
        for (int[] p : pairs) {
            int r = p[0];
            int i = p[1];
            if (cnt[i] == 0) { // 包含 nums[i] 的数字
                empty--;
            }
            cnt[i]++;
            while (empty == 0) { // 每个列表都至少包含一个数
                int l = pairs[left][0];
                if (r - l < ansR - ansL) {
                    ansL = l;
                    ansR = r;
                }
                i = pairs[left][1];
                cnt[i]--;
                if (cnt[i] == 0) { // 不包含 nums[i] 的数字
                    empty++;
                }
                left++;
            }
        }
        return new int[]{ansL, ansR};
    }
}

作者：灵茶山艾府